Partition N items into K bins in Python lazily

Question

Give an algorithm (or straight Python code) that yields all partitions of a collection of N items into K bins such that each bin has at least one item. I need this in both the case where order matters and where order does not matter.

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])]

Example where order does not 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 produce lazy iterators/generators, not lists. Ideally they would use primitives found in itertools. I suspect that there is a clever solution that is eluding me.

While I've asked for this in Python I'm also willing to translate a clear algorithm.

What do you mean by "where order matters"? You seem to treat the items as indistinguishable in that case. — Ronan Lamy, Oct 30 '12 at 14:23
Good question. "Where order matters" could mean several things, If the partition were flattened the items should be in the same order as the input (notice how [[1], [2], [3, 4]] is in the order [1, 2, 3, 4]). The items are distinguishable. So for example the solution [[2], [1], [3, 4]] would not be valid. — MRocklin, Oct 30 '12 at 14:55
In that case, you can decompose the problem into finding the numbers of items, and then generating the lists - for both cases. — Ronan Lamy, Oct 30 '12 at 17:58
In the ordered case, you're looking for [integer compositions](https://en.wikipedia.org/wiki/Composition_%28number_theory%29), and in the unordered one, for [integer partitions](https://en.wikipedia.org/wiki/Integer_partition). I'm not sure what the optimal algorithms are for either, but they're both classical problems. — Ronan Lamy, Oct 30 '12 at 18:10
If you allow empty bins, for your application, those would represent the identities. — asmeurer, Oct 30 '12 at 18:29

score 4 · Answer 1 · answered Oct 30 '12 at 02:40

you need a recursive function to solve this kind of problem: you take the list, take a subportion of it of increasing length and apply the same procedure to the remaining tail of the list in n-1 pieces.

here is my take to the 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]]

[Similar / Related](https://stackoverflow.com/questions/19368375/set-partitions-in-python/30134039#30134039) — mbomb007, May 18 '17 at 14:53

Chris Smith · Accepted Answer · 2012-11-02T21:46:12.783

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

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's 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

Partition N items into K bins in Python lazily

2 Answers2

Linked