Algorithm to produce all partitions of a list in order

Question

I've need for a particular form of 'set' partitioning that is escaping me, as it's not quite partitioning. Or rather, it's the subset of all partitions for a particular list that maintain the original order.

I have a list of n elements [a,b,c,...,n] in a particular order.

I need to get all discrete variations of partitioning that maintains the order.

So, for four elements, the result will be:

[{a,b,c,d}]
[{a,b,c},{d}]
[{a,b},{c,d}]
[{a,b},{c},{d}]
[{a},{b,c,d}]
[{a},{b,c},{d}]
[{a},{b},{c,d}]
[{a},{b},{c},{d}]

---

I need this for producing all possible groupings of tokens in a list that must maintain their order, for use in a broader pattern matching algorithm.

I've found only one other question that relates to this particular issue here, but it's for ruby. As I don't know the language, it looks like someone put code in a blender, and don't particularly feel like learning a language just for the sake of deciphering an algorithm, I feel I'm out of options.

I've tried to work it out mathematically so many times in so many ways it's getting painful. I thought I was getting closer by producing a list of partitions and iterating over it in different ways, but each number of elements required a different 'pattern' for iteration, and I had to tweak them in by hand.

I have no way of knowing just how many elements there could be, and I don't want to put an artificial cap on my processing to limit it just to the sizes I've tweaked together.

Answer 1

You can think of the problem as follows: each of the partitions you want are characterized by a integer between 0 and 2^(n-1). Each 1 in the binary representation of such a number corresponds to a "partition break" between two consecutive numbers, e.g.

 a b|c|d e|f
  0 1 1 0 1

so the number 01101 corresponds to the partition {a,b},{c},{d,e},{f}. To generate the partition from a known parition number, loop through the list and slice off a new subset whenever the corresponding bit it set.

I can understand your pain reading the fashionable functional-programming-flavored Ruby example. Here's a complete example in Python if that helps.

array = ['a', 'b', 'c', 'd', 'e']
n = len(array)

for partition_index in range(2 ** (n-1)):

    # current partition, e.g., [['a', 'b'], ['c', 'd', 'e']]
    partition = []

    # used to accumulate the subsets, e.g., ['a', 'b']
    subset = []

    for position in range(n):

        subset.append(array[position])

        # check whether to "break off" a new subset
        if 1 << position & partition_index or position == n-1:
            partition.append(subset)
            subset = []

    print partition

Answer 2

Here's my recursive implementation of partitioning problem in Python. For me, recursive solutions are always easier to comprehend. You can find more explanation about it in here.

# Prints partitions of a set : [1,2] -> [[1],[2]], [[1,2]] 
def part(lst, current=[], final=[]):
    if len(lst) == 0 :
        if len(current) == 0:
            print (final)
        elif len(current) > 1:
            print ([current] + final)
    else :
        part(lst[1:], current + [lst[0]], final[:])
        part(lst[1:], current[:], final + [[lst[0]]])

Answer 3

Since nobody has mentioned backtrack technique in solving this. Here is the Python solution to solve this using backtrack.

def partition(num):
    def backtrack(index, chosen):
        if index == len(num):
            print(chosen)
        else:
            for i in range(index, len(num)):
                # Choose
                cur = num[index:i + 1]
                chosen.append(cur)

                # Explore
                backtrack(i + 1, chosen)

                # Unchoose
                chosen.pop()

    backtrack(0, [])


>>> partition('123')

['1', '2', '3']
['1', '23']
['12', '3']
['123']

Answer 4

One efficient iterative approach would be to use itertools.combinations to pick which partition indices are in effect, and use itertools.pairwise to iterate through pairs of adjacent partition indices to create list slices. Use itertools.chain to include 0 and None in indices for the first and the last slices:

from itertools import combinations, pairwise, chain, starmap

def partition(lst):
    size = len(lst)
    yield from (
        [lst[s] for s in starmap(slice, pairwise(chain((0,), p, (None,))))]
        for r in range(size) for p in combinations(range(1, size), r)
    )

so that:

print(*partition(list('abcd')), sep='\n')

outputs:

[['a', 'b', 'c', 'd']]
[['a'], ['b', 'c', 'd']]
[['a', 'b'], ['c', 'd']]
[['a', 'b', 'c'], ['d']]
[['a'], ['b'], ['c', 'd']]
[['a'], ['b', 'c'], ['d']]
[['a', 'b'], ['c'], ['d']]
[['a'], ['b'], ['c'], ['d']]