How to iterate through all partitions of a list with a condition on the subsets lenghts

generate all subsets of a list python
find all subsets of a set using recursion python
python powerset
generate all subsets of size k python
generate all sublists of a list python
print all subsets of a set
itertools subsets
java 8 partition(list by size)

For certain purposes, I need to generate an iterable that lists all the partitions of a list, but with a condition on the subsets lenghts. That is, I want to partition my list in subsets of equal lenght (=3 here), except the last one if the lenght of the list isn't a multiple of 3.

i.e. ['a','b','c','d','e'] should give all partitions with 2 subsets of lenght 3 and 2.

Namely, if I simply use :

[p for p in multiset_partitions(['a','b','c','d','e'],2)]
Out: 
[[['a', 'b', 'c', 'd'], ['e']],
[['a', 'b', 'c', 'e'], ['d']],
[['a', 'b', 'c'], ['d', 'e']],
         .....
[['a', 'd'], ['b', 'c', 'e']],
[['a', 'e'], ['b', 'c', 'd']],
[['a'], ['b', 'c', 'd', 'e']]]

I get them all. So my best try so far has been to filter out the partitions that contain at least one subset of lenght > 3 :

from sympy.utilities.iterables import multiset_partitions    

def partitions(liste):
   compte = 0
   n = len(liste)//3 + 1
   for p in multiset_partitions(liste,n):
      l = len(p)
      oversize = False
      i = 0
      while not(oversize) and i != l:
         if len(p[i])>3:
            oversize=True
         i+=1

      if oversize == False:
         compte += 1

      #do something with p

   return(compte) #I'm just counting out the number of partitions right now

This does the trick, but is clearly not the most effective way to achieve what I want. Especially that the number of partitions becomes huge very quickly when the lenght of the list grows.

(10 for a length of 5, but 9100 for 10, 800800 for 13...)

What should be the most efficient pythonic way ?

Thanks in advance,

Thierry

You can always wrap filter around the partitioning function. You can use a lambda function to ensure all of the elements are of length 3 except the last one.

list(filter(lambda x: all(len(z)==3 for z in x[:-1]), multiset_partitions('abcde', 2)))
# returns:
[[['a', 'b', 'c'], ['d', 'e']],
 [['a', 'b', 'd'], ['c', 'e']],
 [['a', 'b', 'e'], ['c', 'd']],
 [['a', 'c', 'd'], ['b', 'e']],
 [['a', 'c', 'e'], ['b', 'd']],
 [['a', 'd', 'e'], ['b', 'c']]]

You will have to be careful when selecting the number of partitions to ensure you are using ceil. I.e for 10 items, you want ceil(10/3) not 10//3.

Python program to get all subsets of given size of a set , Given a set, write a Python program to generate all possible subset of size n of given set within a list. We have already discussed the same problem using Naive approach in this article Python has itertools.combinations(iterable, n) which Return n length subsequences of elements from the input iterable� Linked list of values smaller than x. Linked list of values equal to x. Linked list of values greater than x. Now iterate through the original linked list. If a node’s value is less than x then append it at the end of smaller list. If the value is equal to x, then at the end of equal list. And if value is greater, then at the end of greater list.

Thanks James, I just adapted your filter to keep the items with lenght <=3, and it gives the expected result.

def partitions(liste):

    n = len(liste)//3 + 1            
    return(list(filter(lambda x: all(len(z)<=3 for z in x), multiset_partitions(liste, n))))

And thus,

partitions([1,2,3,4,5])

[[[1, 2, 3], [4, 5]],
[[1, 2, 4], [3, 5]],
[[1, 2, 5], [3, 4]],
[[1, 2], [3, 4, 5]],
[[1, 3, 4], [2, 5]],
[[1, 3, 5], [2, 4]],
[[1, 3], [2, 4, 5]],
[[1, 4, 5], [2, 3]],
[[1, 4], [2, 3, 5]],
[[1, 5], [2, 3, 4]]]

Gives the expected 10 results.

Thanks !

Partition of a set into K subsets with equal sum using BitMask and DP, Partition of a set into K subsets with equal sum using BitMask and DP state mask, the jth element will be added to it based on the following two conditions: given array can be partitioned Iterate over all subsets/masks or Even using Bitwise Operators � Count of binary strings of length N having equal� Ex 3.3.2 Find the generating function for the number of partitions of an integer into distinct odd parts. Find the number of such partitions of 20. Ex 3.3.3 Find the generating function for the number of partitions of an integer into distinct even parts. Find the number of such partitions of 30. Ex 3.3.4 Find the number of partitions of 25 into

Turn partitions into a generator by yielding a partition that matches your criteria on each iteration.

from math import ceil
from sympy.utilities.iterables import multiset_partition

def partitions(liste, m):
    n = ceil(len(liste)/m)
    for p in multiset_partitions(liste,n):
        if not any(list(map(lambda x: len(x) > m, p))):
            yield p

parts = partitions([1,2,3,4,5], 3)
for part in parts:
    print(part)

Partition a List in Java, How to Partition a List using Guava or Apache Commons List<Integer> firstPartition = subSets.iterator().next(); IntStream.range(0, indexes.length - 1) of all “0” elements in the List, then we split the List on these indices. Following are some key ideas for designing recursive function to find total number of valid partitions. If N < K then no partition is possible.; If N < 2*K then only one partition is possible and that is the number N itself.

How to split sequences into subsets in Scala (groupBy, partition , The groupBy , partition , and span methods let you split a sequence into of “the longest prefix of this list whose elements all satisfy p , and the rest of this list. window” over the original sequence, returning sequences of a length given by size. front page alvin on twitter search privacy terms & conditions. If sum of this subset reaches required sum, we iterate for next part recursively, otherwise we backtrack for different set of elements. If number of subsets whose sum reaches the required sum is (K-1), we flag that it is possible to partition array into K parts with equal sum, because remaining elements already have a sum equal to required sum.

2.3 Sequences, That is, there are many kinds of sequences, but they all share common A list value is a sequence that can have arbitrary length. Lists In many cases, we would like to iterate over the elements of a sequence and Another common sequence processing operation is to select a subset of values that satisfy some condition. All Unique Partitions of 2 2 1 1 All Unique Partitions of 3 3 2 1 1 1 1 All Unique Partitions of 4 4 3 1 2 2 2 1 1 1 1 1 1. This article is contributed by Hariprasad NG. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above. Attention reader! Don’t stop learning now.

Partition a set into subsets of size $k$, The list must have a length multiple of l Really lazy search through all partitioned permutations: n = Length@subsets; MapThread[List, {Take[subsets, n/2], select those partitions satisfying the condition about the size of their members. The sys.partitions catalog view gives a list of all partitions for tables and most indexes. Just JOIN that with sys.tables to get the tables. All tables have at least one partition, so if you are looking specifically for partitioned tables, then you'll have to filter this query based off of sys.partitions.partition_number <> 1 (for non

Comments
  • Thanks for your answer. It's ceil indeed. I was using another method before and forgot to change it.
  • So I can see that you assume that the shortest item (if it exists) will always be the last in the partition ! If it is the case then I guess your solution is the best, thanks again !
  • Actually, I had written a//b + 1, which is actually the same than ceil(a/b)
  • Thanks, but I'm afraid this isn't working. Obviously, I'd want to break the "for item" loop when the first item whose length is > 3 is reached (why continue indeed ?). Furthermore, the "yield p" will return every p in the for loop. There should be a boolean trigger (like the one I used) to mark the p's to return...
  • woops. I had worked it out in pseudo code with a none function but I don't think python has any such built-in, hence the sloppy initial re-write. It should be okay now. I actually pasted it into an interpreter. Also incorporated the ceil fix.