Pseudocode or C# algorithm that returns all possible combinations sets for a number of variables

Question

I have 3 variables with some possible values. For example:

Var1 - possible values: 1,2,3
Var2 - possible values: a, b, c 
var3 - possible values: false, true

Can you please help with an approach that returns all possible combinations?

The result be like:

   1,a,false
   1,a,true,
   1,b,false
   1,b,true,
   1,c,false
   1,c,true
   2,a,false
   2,a,true
   2,b,false
   Etc..

I wish the algorithm could apply to any levels of combinations, for example, the algorithm to work on 4 or 5 varibles with other possible values.

Answer 1

The only clean solution is:

have a function mix( A, B ) which takes two lists and returns a list. That's trivial.

Your final code just looks like this:

result = null
result = mix( result, one of your lists );
result = mix( result, another of your lists );
result = mix( result, yet another of your lists );
result = mix( result, yet another list );
result = mix( result, one more list );

example of mix(A,B) ...

mix(A,B)
result = null
for each A
  for each B
    result += AB
return result

Answer 2

Here's something in JavaScript that's pseudocode-like. (I've never coded in C#; maybe I'll try to convert it.)

var sets = [[1,2,3],["a","b","c"],[false,true]],
    result = [];

function f(arr,i){
  if (i == sets.length){
    result.push(arr);
    return;
  }
  for (var j=0; j<sets[i].length; j++){
    _arr = arr.slice(); // make a copy of arr
    _arr.push(sets[i][j]);
    f(_arr,i+1);
  }
}

f([],0)

Output:

console.log(result);

[[1,"a",false]
,[1,"a",true]
,[1,"b",false]
,[1,"b",true]
,[1,"c",false]
,[1,"c",true]
,[2,"a",false]
,[2,"a",true]
,[2,"b",false]
,[2,"b",true]
,[2,"c",false]
,[2,"c",true]
,[3,"a",false]
,[3,"a",true]
,[3,"b",false]
,[3,"b",true]
,[3,"c",false]
,[3,"c",true]]

Answer 3

The simplest solution is to have n nested loops:

for each possible value v1 in var1
    for each possible value v2 in var2
        for each possible value v3 in var3
            print(v1,v2,v3);
        end for v3
    end for v2
end for v1

In more general case, let's assume you have list of lists that contains n lists(one for every var) and each of these lists contains possible values for each variable. You can solve problem with following recursive function all_combinations.

list_of_lists=[[1...][a...][false...]];
current_comb=[];

all_combinations(list_of_lists,current_comb);

function all_combinations(list_of_lists,current_comb)
    if (list_of_lists=[])
        print(current_comb);
        return;
    end if
    current_list=list_of_lists[0];
    remaining_lists=list_of_lists[1:end];
    for each v in current_list
        tmp=current_comb;tmp.Append(v);
        all_combinations(remaining_lists,tmp);
    end for v

Of course when adding variables, soon you will need to deal with combinatorial explosion.

Answer 4

You really ought to look for this elsewhere, and it's not a good stackoverflow question. It's homework and there is an algorithm for this already if you search more using the proper terms.

It's quite simple in fact, if you generalize the algorithm for generating all combinations of digits in a binary string, you should be able to get it:

0 0 0 0 
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0 
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

Notice that the right-most column alternates its values every cell, while the second-from-right column alternates every 2 cells, the next column over from that alternates every 4 cells, and the final digit alternates every 8 cells.

For your case, think of the above as what happens when your sets are:

Var1 - possible values: 0,1
Var2 - possible values: 0,1
Var3 - possible values: 0,1
Var4 - possible values: 0,1

Start a counter that keeps track of your position in each set, and start by cycling through the "rightmost" set a full time before bumping the position of the "next-from-right" set by 1. Continue cycling the the sets in this way, bumping a set when the one to its "right" cycles over, until you've finished cycling the set in the "most significant position". You will have generated all possible combinations in the sets.

The other answers have focused on "give the codez", which really just rewards you for posting your homework question here... so I thought I would at least explain a little.

Answer 5

It looks like you're trying to enumerate Cartesian products. Assuming your items are in list_of_lists, this recursive function in pseudo-code will do it:

enumerate_cartesian_prducts(list_of_lists):

    if list_of_lists is empty:
        return [[]]

    this_list = list_of_lists[0]
    other_lists = list_of_lists[1: ]
    other_cartesian_products = []
    return [(e + other_cartesian_product) \
        for e in this_list and other_cartesian_product in other_cartesian_products]

Note how the last line would probably be a double loop in most languages: it iterates over all the elements in the first list, all the lists in the cartesian products of the rest, and creates a list of all the appended results.

Answer 6

Assume that each variable has a set or vector associated with is. That is: set1 = [1, 2, 3] set2 = [a, b, c] set3 = [F, T]

Then, one way is to loop over these sets in nested "for" loops. Assume that your output structure is a list of 3-element lists. That is, your output desired looks like this: [[1,a,F], [1,a,T], [1,b,F],......] Also assume that (like in Python) you can use a function like "append" to append a 2-element list to your big list. Then try this:

myList = []  #empty list
for i in set1:
  for j in set2:
    for k in set3:
      myList.append([i, j, k])  #Appends 3-element list to big list

You may need to do a deepcopy in the append statement so that all the i's, j's, and k's arene't updated in your master list each time you run through an iteration. This may not be the most efficient, but I think it's relatively straightforward.