algorithmsetpartitioning

# Algorithm to produce all partitions of a list in order

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.

Solution

• 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
``````