Register to reply

Enumerating Combinations

by Soveraign
Tags: combinations, enumerating
Share this thread:
Soveraign
#1
Feb23-11, 12:51 PM
P: 54
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
Phys.Org News Partner Science news on Phys.org
Hoverbike drone project for air transport takes off
Earlier Stone Age artifacts found in Northern Cape of South Africa
Study reveals new characteristics of complex oxide surfaces
rcgldr
#2
Feb23-11, 02:03 PM
HW Helper
P: 7,032
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.


Register to reply

Related Discussions
Combinations (How many combinations contain specific numbers)? Calculus & Beyond Homework 2
Combinations/permutations help Precalculus Mathematics Homework 3
Math combinations help Precalculus Mathematics Homework 1
Possible Combinations Set Theory, Logic, Probability, Statistics 5
Sum of Combinations Set Theory, Logic, Probability, Statistics 12