How To Iterate Through All Partitions Of A List With A Condition On The Subsets Lenghts

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 s

Solution 1:

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.

Solution 2:

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 !

Solution 3:

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)