Splitting N items into K-boxes in Python is lazy

Question

Give an algorithm (or direct Python code) that gives all sections of a collection of N elements in K-rolls, so that each bit has at least one element. I need this as in the case when the order matters, and where the order does not matter.

An example where order matters

>>> list(partition_n_in_k_bins_ordered((1,2,3,4), 2)) [([1], [2,3,4]), ([1,2], [3,4]), ([1,2,3], [4])] >>> list(partition_n_in_k_bins_ordered((1,2,3,4), 3)) [([1], [2], [3,4]), ([1], [2,3], [4]), ([1,2], [3], [4])] >>> list(partition_n_in_k_bins_ordered((1,2,3,4), 4)) [([1], [2], [3], [4])] 

An example where order doesn't matter

 >>> list(partition_n_in_k_bins_unordered({1,2,3,4}, 2)) [{{1}, {2,3,4}}, {{2}, {1,3,4}}, {{3}, {1,2,4}}, {{4}, {1,2,3}}, {{1,2}, {3,4}}, {{1,3}, {2,4}}, {{1,4}, {2,3}}] 

These functions should create lazy iterators / generators, not lists. Ideally, they would use the primitives found in itertools . I suspect there is a smart solution that eludes me.

While I requested this in Python, I am also ready to translate a clear algorithm.

Answer 1

The Enrico, Knuth's algorithm and just my glue are needed to put together something that returns a list of lists or a set of sets (returned as lists of lists in case the elements are not hashed).

 def kbin(l, k, ordered=True): """ Return sequence ``l`` partitioned into ``k`` bins. Examples ======== The default is to give the items in the same order, but grouped into k partitions: >>> for p in kbin(range(5), 2): ... print p ... [[0], [1, 2, 3, 4]] [[0, 1], [2, 3, 4]] [[0, 1, 2], [3, 4]] [[0, 1, 2, 3], [4]] Setting ``ordered`` to None means that the order of the elements in the bins is irrelevant and the order of the bins is irrelevant. Though they are returned in a canonical order as lists of lists, all lists can be thought of as sets. >>> for p in kbin(range(3), 2, ordered=None): ... print p ... [[0, 1], [2]] [[0], [1, 2]] [[0, 2], [1]] """ from sympy.utilities.iterables import ( permutations, multiset_partitions, partitions) def partition(lista, bins): # EnricoGiampieri partition generator from # http://stackoverflow.com/questions/13131491/ # partition-n-items-into-k-bins-in-python-lazily if len(lista) == 1 or bins == 1: yield [lista] elif len(lista) > 1 and bins > 1: for i in range(1, len(lista)): for part in partition(lista[i:], bins - 1): if len([lista[:i]] + part) == bins: yield [lista[:i]] + part if ordered: for p in partition(l, k): yield p else: for p in multiset_partitions(l, k): yield p 

Answer 2

you need a recursive function to solve this problem: you take a list, take it longer and apply the same procedure to the remaining tail of the list in n-1 parts.

here is my trick to an ordered combination

 def partition(lista,bins): if len(lista)==1 or bins==1: yield [lista] elif len(lista)>1 and bins>1: for i in range(1,len(lista)): for part in partition(lista[i:],bins-1): if len([lista[:i]]+part)==bins: yield [lista[:i]]+part for i in partition(range(1,5),1): print i #[[1, 2, 3, 4]] for i in partition(range(1,5),2): print i #[[1], [2, 3, 4]] #[[1, 2], [3, 4]] #[[1, 2, 3], [4]] for i in partition(range(1,5),3): print i #[[1], [2], [3, 4]] #[[1], [2, 3], [4]] #[[1, 2], [3], [4]] for i in partition(range(1,5),4): print i #[[1], [2], [3], [4]]