Loop through different sets of unique permutations

Question

I'm having a hard time getting started to layout code for this problem.

I have a fixed amount of random numbers, in this case 8 numbers. R[] = { 1, 2, 3, 4, 5, 6, 7, 8 };

That are going to be placed in 3 sets of numbers, with the only constraint that each set contain minimum one value, and each value can only be used once. Edit: all 8 numbers should be used

For example:

R1[] = { 1, 4 }

R2[] = { 2, 8, 5, 6 }

R3[] = { 7, 3 }

I need to loop through all possible combinations of a set R1, R2, R3. Order is not important, so if the above example happened, I don't need

R1[] = { 4, 1 }

R2[] = { 2, 8, 5, 6 }

R3[] = { 7, 3 }

NOR

R1[] = { 2, 8, 5, 6 }

R2[] = { 7, 3 }

R3[] = { 1, 4 }

What is a good method?

Answer 1

I have in front of me Knuth Volume 4, Fascicle 3, Generating all Combinations and Partitions, section 7.2.1.5 Generating all set partitions (page 61 in fascicle).

First he details Algorithm H, Restricted growth strings in lexicographic order due to George Hutchinson. It looks simple, but I'm not going to dive into it just now.

On the next page under an elaboration Gray codes for set partitions he ponders:

Suppose, however, that we aren't interested in all of the partitions; we might want only the ones that have m blocks. Can we run this through the smaller collection of restricted growth strings, still changing one digit at a time?

Then he details a solution due to Frank Ruskey.

The simple solution (and certain to be correct) is to code Algorithm H filtering on partitions where m==3 and none of the partitions are the empty set (according to your stated constraints). I suspect Algorithm H runs blazingly fast, so the filtering cost will not be large.

If you're implementing this on an 8051, you might start with the Ruskey algorithm and then only filter on partitions containing the empty set.

If you're implementing this on something smaller than an 8051 and milliseconds matter, you can seed each of the three partitions with a unique element (a simple nested loop of three levels), and then augment by partitioning on the remaining five elements for m==3 using the Ruskey algorithm. You won't have to filter anything, but you do have to keep track of which five elements remain to partition.

The nice thing about filtering down from the general algorithm is that you don't have to verify any cleverness of your own, and you change your mind later about your constraints without having to revise your cleverness.

I might even work a solution later, but that's all for now.

P.S. for the Java guppies: I discovered searching on "George Hutchison restricted growth strings" a certain package ca.ubc.cs.kisynski.bell with documentation for method growthStrings() which implements the Hutchison algorithm.

Appears to be available at http://www.cs.ubc.ca/~kisynski/code/bell/