How To Find All Partitions Of A List S Into K Subsets (can Be Empty)?

I have a list of unique elements, let's say [1,2], and I want to split it onto k=2 sublists. Now I want to have all possible sublists: [ [ [1,2],[] ], [ [1],[2] ], [ [2],[1] ], [

Solution 1:

Here is an alternative solution:

defpartition_k(l, k):
    n = len(l)
    if k > n:
        raise ValueError("k = {0} should be no more than n = {1}".format(k, n))

    if n == 0:
        yield []
        return

    pos = [0] * n
    whileTrue:
        # generate output for the value
        out = [[] for _ inrange(k)]
        for i inrange(n):
            out[pos[i]].append(l[i])
        yield out

        #increment the value
        pos[0] += 1for i inrange(n):
            # should we carry from this digit to the next one?if pos[i] == k:
                # overflow of the whole value?if i == n - 1:
                    return
                pos[i] = 0
                pos[i + 1] += 1else:
                break

Let n be the length of the list and k is the number of partitions. The idea behind this code is that each line of the output can be represented as a number of n digits in base-k system. Each "digit" shows in which bucket goes the value at corresponding position. For example line

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

can be encoded as [1,0,0,2] which means

• 1 goes to the bucket #1
• 2 goes to the bucket #0
• 3 goes to the bucket #0
• 4 goes to the bucket #2

Obviously every such n-digits base-k number represents a valid partition of the list and each partition is represented by some number. So to generate all partitions we need just iterate through all such numbers and generate corresponding partitions. It is easier to do if you use a list of digits to represent a number (in the code this is pos).