Permutation o N elements in A boxes?

Question

I'm trying to find all possible ways to arrange N elements in A boxes, where doesn't matter the order of the boxes and the order of the elements, but it does matter which elements are together at the same box. For example, the expected result for 3 box and 3 elements is bellow:

            box_1       box_2      box_3
case-1      [1,2,3]    []          []
case-2      [1,2]      [3]         []
case-3      [1,3]      [2]         []
case-4      [2,3]      [1]         []
case-5      [1]        [2]         [3]

This is a similar but more more general problem than the one asked here: Enumeration of combinations of N balls in A boxes?

I would be very grateful for any contribution to this question, preferably using python language.

score 0 · Accepted Answer · edited May 23 '17 at 12:24

These are called set partitions. A recursive function can be found here: Set partitions in Python. A slightly more efficient "bottom-up" recursive version is this:

def generate_partitions(a):
    a = list(a)
    n = len(a)
    partition = [] # a list of lists, currently empty

    def assign(i):
        if i >= n:
            yield [list(part) for part in partition]
        else:
            # assign a[i] to an existing part
            for part in partition:
                part.append(a[i])
                yield from assign(i + 1)
                part.pop()

            # assign a[i] to a completely new part
            partition.append([a[i]])
            yield from assign(i + 1)
            partition.pop()

    if n:
        yield from assign(0)
    else:
        yield [[]]


for partition in generate_partitions([1,2,3]):
    print(*partition)

Output:

[1, 2, 3]
[1, 2] [3]
[1, 3] [2]
[1] [2, 3]
[1] [2] [3]

This does not produce the empty boxes as in your example, but it trivial to augment the generator to do so.

For an iterative algorithm, see "Efficient Generation of Set Partitions" by Michael Orlov (2002). Note that the number of set partitions grows very quickly, so even an iterative algorithm will take some time to enumerate all the partitions of even a modest-sized set.

To count the number of set partitions without generating them, see the Bell Numbers (OEIS A000110). Here is one possible (not very efficient) procedure to compute Bell numbers in Python:

def bell(n):
    "-> the n'th Bell number."
    assert n >= 0, n

    # loop will execute at least once
    for b in bell_sequence(n): 
        pass 

    return b

def bell_sequence(n):
    """Yields the Bell numbers b(0),b(1)...b(n).

    This function requires O(n) auxiliary storage.
    """
    assert n >= 0, n
    # compute Bell numbers using the triangle scheme
    yield 1 # b(0)

    row = [1] + (n-1)*[0]

    for i in range(0, n):
        row[i] = row[0]

        for k in reversed(range(i)):
            row[k] += row[k + 1]

        yield row[0] # b(i + 1)

Permutation o N elements in A boxes?

1 Answers1