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']