generate all partitions of a set

Question

For a set of the form A = {1, 2, 3, ..., n}. It is called partition of the set A, a set of k<=n elements which respect the following theorems:

a) the union of all the partitions of A is A

b) the intersection of 2 partitions of A is the empty set (they can't share the same elements).

For example. A = {1, 2,... n} We have the partitions:

{1, 2, 3}
{1, 2} {3}
{1, 3} {2}
{2, 3} {1}
{1} {2} {3}

These theoretical concepts are presented in my algorithms textbook (by the way, this subchapter is part of the "Backtracking" chapter). I am supposed to find an algorithm to generate all the partitions of a given set. I was struggling with this problem all the day and I couldn't find a solution. Can you explain me how does this algorithm work? Also, can you give me a pseudo-code sketch of the algorithm?

Answer 1

There is an important observation (in a comment) that a partition of a set of n elements can be represented as an integer sequence of the form [p₁, … p_n] where p_i is the partition number of element i. For such a sequence to be valid, it must obey the rules that p₁ is 1, and for every j where 1 < j ≤ n, there is some i < j such that p_j ≤ p_i&plus;1. Or in other words, in any prefix of the sequence, no integer is skipped.

Now, there is a standard algorithm for enumerating constrained sequences in lexicographical order, which consists of the following:

• Start with the smallest sequence.
• To find the next sequence in lexicographical order:
  • Scan backwards over the sequence and find the rightmost "incrementable" element. (An incrementable element is an element such that there is some larger element which could be substituted for that element, and the resulting subsequence up to that point is a prefix of at least one valid sequence.)
  • Change that element to the next larger element which is viable (i.e. which results in a valid prefix, as above), and then fill in the remaining elements to its right (if any) with the smallest possible values.
  • If there is no incrementable element, then the enumeration has terminated.

With several provisions about the search for an incrementable element, this algorithm is at worst O(n) and it is often O(1) when the element to be incremented is usually close to the end of the sequence. (For example, using this algorithm to enumerate permutation is O(1) to find the next permutation as long as you can find the "next element" in O(1).)

In order to apply this algorithm to the partition case, we observe the following:

1. The smallest possible sequence is [1, … 1]
2. An element p_i is incrementable provided that:
   • p_i<n
   • There is some j<i such that p_i&equals;p_j
3. The smallest suffix of a viable prefix is [1, … 1]

Another way of stating the condition in observation 2 is that an element is incrementable unless its value is n or it is the first element in the sequence with its value. We can make that determination in O(1) if we also maintain the sequence [m₁, … m_n] where m₁ is 0, and m_i is the maximum of m_i-1 and p_i-1. m is trivial to maintain, and it allows us to rewrite the incrementability condition as simply p_i≤m_i.

It is easy to see that Next Partition can be implemented in O(n) time, but as it happens it is also the case that it is amortized time O(1). Roughly speaking, that is because in most cases, the last element of the sequence is incrementable.

Answer 2

You can try the recursive answer if your set is not to big (or else use stack) :

The principle is the following, you have a function that give back :

rec_func(SET) = List of List of Set

And work as follow :

rec_func(SET) =
  if SET = {empty}:
    // if no element, easy to give the answer
    return([[]])
  else:
    // 1. Remove one element from the set : 'a' to this set
    a = SET.pop()
    // 2. Call rec_func :
    list_of_list_of_set = rec_func(SET\'a')  
    response = []
    // 3. For every possibilities given by the function add the element 'a' :
    For every list_of_set in list_of_list_of_set  :
       // Case 1, you add 'a' to list_of_set
       response.push( [{'a'} + list_of_set] )
       // Case 2, for every set, you create a copy where you add 'a'
       for every set in list_of_set:
           response.push( [{set,'a'} + list_of_set\set] )

    // The function return the list of list of set created.        
    return(response)

Answer 3

I was working on an efficient algorithm that produces all partitions of a set as described before based on the keyword approach defined by @rici. The following algorithm, written in python, does it and there is still optimization possible. I am on it. As you may know, this problem is NP-complete! Due to optimization there is maybe some strange notation like the try/except. However, the n and k variables are there to define via n, how many different elements the set has and the k is the amount of different classes the sets are allowed to have. INFO: the algorithm generates ALL partitions UP TO the amount of different classes not exclusively those classes!!!

def partitions():
        global n
        global k
        codeword = [1 for digitIndex in range(0, n)]
        while True:
                print codeword
                startIndex = n - 1
                while startIndex >= 0:
                        maxValue = max(codeword[0 : startIndex])
                        if codeword[startIndex] > maxValue or maxValue > k or codeword[startIndex] >= k:
                                codeword[startIndex] = 1
                                startIndex -= 1
                        else:
                                codeword[startIndex] += 1
                                break

n = 12
k = 2
try:
        partitions()
except:
        pass