kilabit.info
Simple | Small | Stable | Secure

Generating Partition of A Set

Problem: given a set of discrete value {A,B,C} generate k partition of set where there is no empty partition and no duplicate value exist in subset of a partition.

Rules:

  • No empty subset is returned.

  • No duplicate value exist in each partitions, i.e. when partitioning into two subset, if subset one contain {A} and then the another subset must not contain {A}

  • If k is 1 return the original set.

  • If k is equal to number of value in set, return each element of set as a partition and as a subset.

Example:

Given input set {A,B,C}, if k is 1 then the number of generated partition is 1 which is equal to original set: {A,B,C}. If k is 2 then the number of generated partition is 3 which consist of {{A},{BC}}, {{B},{C,D}}, and {{C},{A,B}}. If k is three then the number of generated partition is 3 which consist of {{A},{B},{C}}.

Another example, given input set {A,B,C,D}, if k is 1 then the number of generated partition is 1: {A,B,C,D}. If k is 2 then the number of generated partition is 7, which is {{A},{B,C,D}}, {{B},{A,C,D}}, {{C},{A,B,D}}, {{D},{A,B,C}}, {{A,B},{C,D}}, {{A,C},{B,D}}, {{A,D},{B,C}}. If k is 3 then the number of generated partition is 6, which is {{A},{B},{C,D}}, {{A},{C},{B,D}}, {{A}{D}{B,C}}, {{A,B},{C},{D}}, {{A,C},{B},{D}}, {{A,D},{B},{C}}. If k is 4 then the number of possible generated partition is 4: {{A},{B},{C},{D}}

In mathematics, this problem is known as subproblem of combinatrics where the number of partition can be computed using "Stirling number of the second way" [1], which take n objects and the number of partition or k, and return number of possible partition of n using k. In computer science, the problem is called "Partition of a set".

If you are a thinker and interested on solving this problem, go ahead, grab some paper and a pencil and close this journal.

* * *

Now, back to the problem. This is an old problem, oldest than computer it self. There are more papers out there which trying to be a fastest algorithm using iterative or parallel method (of course the last paper is the winner). Some of them using sequence of bit to mark wether a value is a group of partition. Here is the gist of it, given three value with two partition the possible sequence of bits are,

0 0 0 = 1 partition
0 0 1 = 2 partition
0 1 0 = 2 partition
0 1 1 = 2 partition
1 0 0 = 2 partition
1 0 1 = 2 partition
1 1 0 = 2 partition
1 1 1 = 3 partition

Can you see the pattern? The 0's bit is group one and 1's bit is another group. There are some problem with this solution: first, we must check for duplicate partition, i.e. 001 is duplicate with 110. Second problem, we must generate all bit for all values, for example partition with 3 subset is generated even if we only need 2 partitions.

There is another alternative without needed to check for duplicate and does not waste than k defined partition. The solution is using recursive function. Here is the algorithm,

Function name: partition

Input:

  • A: set of value

  • k: number of partition

Output:

P: a set contain subsets of A into k possible partition without an empty set and duplicate value.

Process:

(1) If k equal 1, then return A

(2) if k equal to length of A, then

(2.1) create new set A'

(2.2) for each value in A as a

(2.2.1) create new partition p contain only a

(2.2.2) add p to the new set A'

(2.2.3) return A'

(3) Create new set B for partitions

(4) move the first elemen of A to a1, which make A contain n-1 element.

(5) call function partition with parameter A and k, save the result to A'

(6) for each partition in A' as p

(6.1) for each subset in p as sub

(6.1.1) create new partition p' by joining element a1 with subset sub and add it to B

(7) call function partition with parameter A and k-1, save the result to A''

(8) for each partition in A'' as p

(8.1) create new partition p' by appending element a1 as subset to partition p and add it to B

(9) return B

Procedurally, if we give set {A,B,C} with 2 as partition number and call and print the algorithm, we will see the output like these,

partition({A,B,C},2)
  B:{}
  A: partition({B,C},2)
    B:{{B},{C}}
    return {B},{C}
  B:{{{B,A},{C}},{{B},{C,A}}
  A: partition({B,C},1)
    return {B,C}
  B:{{{B,A},{C}},{{B},{C,A}},{{B,C},{A}}
  return B

Simple.