Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

generate all partitions of a set [closed]

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?

like image 763
cristid9 Avatar asked Jun 17 '15 13:06

cristid9


People also ask

How many partitions can we form in a 5 element set?

The 52 partitions of a set with 5 elements. A colored region indicates a subset of X that forms a member of the enclosing partition. Uncolored dots indicate single-element subsets.

How many partitions are there in a set of 4 elements?

This picture by Tilman Piesk shows the 15 partitions of a 4-element set, ordered by refinement.

How many partitions are there in a set of 3 elements?

Hence a three-element set {a,b,c} has 5 partitions: {a,b,c}


2 Answers

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 [p1, … pn] where pi is the partition number of element i. For such a sequence to be valid, it must obey the rules that p1 is 1, and for every j where 1 < jn, there is some i < j such that pjpi&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 pi is incrementable provided that:
    • pi<n
    • There is some j<i such that pi&equals;pj
  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 [m1, … mn] where m1 is 0, and mi is the maximum of mi-1 and pi-1. m is trivial to maintain, and it allows us to rewrite the incrementability condition as simply pimi.

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.

like image 118
rici Avatar answered Oct 13 '22 18:10

rici


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)
like image 34
Emmanuel Jay Avatar answered Oct 13 '22 18:10

Emmanuel Jay