Generate all set splits

Question

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

a) the union of all partitions on A is equal to A

b) the intersection of two sections A is an empty set (they cannot use the same elements).

For example. A = {1, 2,... n} We have sections: {1, 2, 3} {1, 2} {3} {1, 3} {2} {2, 3} {1} {1} {2} {3}

These theoretical concepts are presented in the textbook on my algorithms (by the way, this subsection is part of the "Rollback" chapter). I have to find an algorithm to generate all sections of this set. I struggled with this problem all day and I could not find a solution. Can you explain to me how this algorithm works? 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 large (or use the stack):

The principle is this: you have a function that returns:

 rec_func(SET) = List of List of Set 

And work as follows:

 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 2

There is an important observation (in the commentary) that splitting a set of elements n can be represented as an integer sequence of the form [p ₁ , & hellip; p _n ], where p _i is the section number of the element i. For such a sequence to be valid, it must obey the rules that p ₁ is 1, and for each j, where 1 <j & le; n, there exists some i <j such that p _j & le; p <sub> yasub> & plus; 1. Or, in other words, in any sequence prefix, no integer is skipped.

Now there is a standard algorithm for listing limited sequences in lexicographic order, which consists of the following:

• Start with the least sequence.
• To find the following sequence in lexicographical order:
  • Scan back through the sequence and find the rightmost "incremental" element. (An incremental element is an element such that there is some larger element that can be replaced for this element, and the resulting subsequence to this point is a prefix of at least one valid sequence.)
  • Change this item to the next larger item, which is viable (i.e. which results in a valid prefix as above), and then fill in the remaining items on the right (if any) with the smallest possible values.
  • If there is no incremental element, then the enumeration is completed.

With several provisions for finding an incremental element, this algorithm is O (n) in the worst case, and often O (1), when the element to be enlarged is usually near the end of the sequence. (For example, using this algorithm to enumerate permutations is O (1) to find the next permutation if you can find the “next element” in O (1).)

To apply this algorithm to the case of a section, we note the following:

• The smallest possible sequence is [1, & hellip; one]
• An element p _i is incremental if:
  • p <sub> Isub> <p
  • There is some j <i such that p _i & is equal to; p _j
• The smallest suffix of a viable prefix is ​​[1, & hellip; one]

Another way to state the condition in observation 2 is that an element is incremental if its value is n or it is the first element in the sequence with its value. We can make this definition in O (1) if we also keep the sequence [m ₁ , & hellip; m _n ], where m ₁ is 0, and m _i is the maximum m _i-1 and p <sub> I-1sub>. m is trivial to support, and this allows us to rewrite the increment condition as simply p _i & le; m _i .

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

Answer 3

I worked on an efficient algorithm that creates all sections of a set, as described above, based on a keyword defined by @rici. The following algorithm, written in python, does this, and there is still the possibility of optimization. I am on it. As you know, this problem is NP-complete! Due to the optimization, there may be some strange notation, for example try / except. However, the variables n and k must determine through n how many different elements the set has, and k is the number of different classes that are allowed to have the set. INFO: the algorithm generates ALL sections up to the number of different classes of not only these 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