How can I maximally partition a set?

Question

I'm trying to solve one of the Project Euler problems. As a consequence, I need an algorithm that will help me find all possible partitions of a set, in any order.

For instance, given the set 2 3 3 5:

2 | 3 3 5
2 | 3 | 3 5
2 | 3 3 | 5
2 | 3 | 3 | 5
2 5 | 3 3

and so on. Pretty much every possible combination of the members of the set. I've searched the net of course, but haven't found much that's directly useful to me, since I speak programmer-ese not advanced-math-ese.

Can anyone help me out with this? I can read pretty much any programming language, from BASIC to Haskell, so post in whatever language you wish.

Answer 1

Have you considered a search tree? Each node would represent a choice of where to put an element and the leaf nodes are answers. I won't give you code because that's part of the fun of Project Euler ;)

Answer 2

Well, the problem has two aspects.

Firsty, the items can be arranged in any order. So for N items, there are N! permutations (assuming the items are treated as unique).
Secondly, you can envision the grouping as a bit flag between each item indicating a divide. There would be N-1 of these flags, so for a given permutation there would be 2^(N-1) possible groupings.
This means that for N items, there would be a total of N!*(2^(N-1)) groupings/permutations, which gets big very very fast.

In your example, the top four items are groupings of one permutation. The last item is a grouping of another permutation. Your items can be viewed as :

2 on 3 off 3 off 5
2 on 3 on 3 off 5
2 on 3 off 3 on 5
2 on 3 on 3 on 5
2 off 5 on 3 off 3

The permutations (the order of display) can be derived by looking at them like a tree, as mentioned by the other two. This would almost certainly involve recursion, such as here. The grouping is independent of them in many ways. Once you have all the permutations, you can link them with the groupings if needed.

Answer 3

I quickly whipped up some code to do this. However, I left out separating every possible combination of the given list, because I wasn't sure it was actually needed, but it should be easy to add, if necessary.

Anyway, the code runs quite well for small amounts, but, as CodeByMoonlight already mentioned, the amount of possibilities gets really high really fast, so the runtime increases accordingly.

Anyway, here's the python code:

import time

def separate(toseparate):
  "Find every possible way to separate a given list."
  #The list of every possibility
  possibilities = []
  n = len(toseparate)
  #We can distribute n-1 separations in the given list, so iterate from 0 to n
  for i in xrange(n):
    #Create a copy of the list to avoid modifying the already existing list
    copy = list(toseparate)
    #A boolean list indicating where a separator is put. 'True' indicates a separator
    #and 'False', of course, no separator.
    #The list will contain i separators, the rest is filled with 'False'
    separators = [True]*i + [False]*(n-i-1)
    for j in xrange(len(separators)):
      #We insert the separators into our given list. The separators have to
      #be between two elements. The index between two elements is always
      #2*[index of the left element]+1.
      copy.insert(2*j+1, separators[j])
    #The first possibility is, of course, the one we just created
    possibilities.append(list(copy))
    #The following is a modification of the QuickPerm algorithm, which finds
    #all possible permutations of a given list. It was modified to only permutate
    #the spaces between two elements, so it finds every possibility to insert n
    #separators in the given list.
    m = len(separators)
    hi, lo = 1, 0
    p = [0]*m
    while hi < m:
      if p[hi] < hi:
        lo = (hi%2)*p[hi]
        copy[2*lo+1], copy[2*hi+1] = copy[2*hi+1], copy[2*lo+1]
        #Since the items are non-unique, some possibilities will show up more than once, so we
        #avoid this by checking first.
        if not copy in possibilities:
          possibilities.append(list(copy))
        p[hi] += 1
        hi = 1
      else:
        p[hi] = 0
        hi += 1
  return possibilities

t1 = time.time()
separations = separate([2, 3, 3, 5])
print time.time()-t1
sepmap = {True:"|", False:""}
for a in separations:
  for b in a:
    if sepmap.has_key(b):
      print sepmap[b],
    else:
      print b,
  print "\n",

It's based on the QuickPerm algorithm, which you can read more about here: QuickPerm

Basically, my code generates a list containing n separations, inserts them into the given list and then finds all possible permutations of the separations in the list.

So, if we use your example we would get:

2  3  3  5 
2 | 3  3  5 
2  3 | 3  5 
2  3  3 | 5 
2 | 3 | 3  5 
2  3 | 3 | 5 
2 | 3  3 | 5 
2 | 3 | 3 | 5

In 0.000154972076416 seconds.

However, I read through the problem description of the problem you are doing and I see how you are trying to solve this, but seeing how quickly the runtime increases I don't think that it would work as fast you would expect. Remember that Project Euler's problems should solve in around a minute.

Answer 4

In general I would look at the structure of the recursion used to compute the number of configurations, and build a similar recursion for enumerating them. Best is to compute a one-to-one mapping between integers and configurations. This works well for permutations, combinations, etc. and ensures that each configuration is enumerated only once.

Now even the recursion for the number of partitions of some identical items is rather complicated.

For partitions of multisets the counting amounts to solving the generalization of Project Euler problem 181 to arbitrary multisets.

Answer 5

Take a look at:

The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions

7.2.1.5. Generating all set partitions