Efficient Algorithm for Enumerating Combinations

[Soveraign]

I am facing an issue in my research where I need to enumerate all combinations of an underlying set. BUT the set has some special features. Here is an example:

Given a set {A,B,C,D,E, F} where each item in the set consists of two values. Something like:

A = (1,2)
B = (3,4)
C = (5,6)
D = (1,6)
E = (3,5)
F = (1,3)

Now, my task is to generate (quickly) all combinations of the items in the set where you use the underlying numbers at most once. In the above example, the resulting subsets would be:

{A, B, C}
{A, E}
{B, D}
{C, B}
{D, B}
{D, E}

...and maybe a few others. But hopefully this illustrates what I mean. When starting this problem, I implemented a very inefficient (but complete) recursive algorithm that enumerated all combinations (including order) and just eliminated the duplicates. But this has proven to be untenable now that my set size is in the 30's and the underlying set of numbers is nearly 20.

I realize that this specific problem has maybe not been pursued in Comp Sci, and that it can be considered a special case of n choose m where order doesn't matter. So my question to you all would be, what is the most efficient n choose m algorithm out there (for unordered sets)? or even better, has my problem been solved by someone else already?

Thanks!
Brian

 

[rcgldr]

You could generate a set of binary arrays for each set, where the arrays represent valid combinations (0=invalid because of duplicate, 1=valid because no duplicates). Using your example:

array[0] = {0, 1, 1, 0, 1, 0} // A|A no A|B yes A|C yes A|D no A|E yes A|F no
array[1] = {1, 0, 1, 1, 0, 0} // B|A yes B|B no B|C yes B|D yes B|E no B|F no
...

then for each loop that tests all combinations, you can "and" the arrays for specific combinations. For example, when testing A|B|?, you can "and" array[0] & arrray[1] to get an arrary of 0's and 1's for all sets that are not duplicates of A|B.

You might want an APL like reduction function to generate a variable length array of indexes

{0 1 1 0 1 0} / {0 1 2 3 4 5} => {1 2 4}
{1 0 1 1 0 0} / {0 1 2 3 4 5} => {0 2 3}
{0 1 0 0 0 1} / {0 1 2 3 4 5} => {1 5}
{0 0 0 0 0 0} / {0 1 2 3 4 5} => {}

For C, you'd need to store the length of an array of indexes:

Not sure what else you could do here.