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