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

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)