Algorithm for dynamic combinations

My code has a list called INPUTS, that contains a dynamic number of lists, let's call them A, B, C, .. N. These lists contain a dynamic number of Events

I would like to call a function with each combination of Events. To illustrate with an example:

INPUTS: A(0,1,2), B(0,1), C(0,1,2,3)

I need to call my function this many times for each combination (the input count is dynamic, in this example it is three parameter, but it can be more or less)

function(A[0],B[0],C[0]) 
function(A[0],B[1],C[0]) 
function(A[0],B[0],C[1])
function(A[0],B[1],C[1])
function(A[0],B[0],C[2]) 
function(A[0],B[1],C[2])
function(A[0],B[0],C[3])
function(A[0],B[1],C[3])

function(A[1],B[0],C[0]) 
function(A[1],B[1],C[0]) 
function(A[1],B[0],C[1])
function(A[1],B[1],C[1])
function(A[1],B[0],C[2]) 
function(A[1],B[1],C[2])
function(A[1],B[0],C[3])
function(A[1],B[1],C[3])

function(A[2],B[0],C[0]) 
function(A[2],B[1],C[0]) 
function(A[2],B[0],C[1])
function(A[2],B[1],C[1])
function(A[2],B[0],C[2]) 
function(A[2],B[1],C[2])
function(A[2],B[0],C[3])
function(A[2],B[1],C[3])

This is what I have thought of so far: My approach so far is to build a list of combinations. The element combination is itself a list of "index" to the input arrays A, B and C. For our example:

my list iCOMBINATIONS contains the following iCOMBO lists

(0,0,0) 
(0,1,0) 
(0,0,1)
(0,1,1)
(0,0,2) 
(0,1,2)
(0,0,3)
(0,1,3)

(1,0,0) 
(1,1,0)  
(1,0,1) 
(1,1,1)
(1,0,2) 
(1,1,2)
(1,0,3) 
(1,1,3)

(2,0,0)
(2,1,0)  
(2,0,1) 
(2,1,1)
(2,0,2) 
(2,1,2)
(2,0,3) 
(2,1,3)

Then I would do this:

foreach( iCOMBO in iCOMBINATIONS)
{
      foreach ( P in INPUTS )
      {
    开发者_JAVA技巧       COMBO.Clear()
           foreach ( i in iCOMBO )
           {
                 COMBO.Add( P[ iCOMBO[i] ] )
           }
           function( COMBO ) --- (instead of passing the events separately)
      }
}

But I need to find a way to build the list iCOMBINATIONS for any given number of INPUTS and their events. Any ideas?

Is there actually a better algorithm than this? any pseudo code to help me with will be great.

C# (or VB)

Thank You

---

You can use an array to hold the indexes for each list. Example:

List<List<int>> lists = new List<List<int>> {
  new List<int> { 0,1,2 },
  new List<int> { 0,1 },
  new List<int> { 0,1,2,3 }
};

int[] cnt = new int[lists.Count];
int index;
do {
  Console.WriteLine(String.Join(",", cnt.Select((c,i) => lists[i][c].ToString()).ToArray()));
  index = cnt.Length - 1;
  do {
    cnt[index] = (cnt[index] + 1) % lists[index].Count;
  } while(cnt[index--] == 0 && index != -1);
} while (index != -1 || cnt[0] != 0);

---

This is permutation problem. You may take a look at this:

http://www.interact-sw.co.uk/iangblog/2004/09/16/permuterate

---

I had similar problem some time ago (generating combinations), I've used code from: http://www.merriampark.com/comb.htm . It's java, but I hadn't any problems to translate it into C#.

---

Put A,B,C in matrix! M=[A,B,C]

recursive_caller(d,params):
    if d == len(M):
        function(params)
        return

    for i in M[d]:
        params[d]=i
        recursive_caller(d+1,params)

---

It would seem that what you really want, is neither a permutation, nor a combination, per se. You want to look at the cartesian product (see here) of several sets, the iteration over which may involve iterating through combinations of individual sets.

However, this is unlike a combination problem, because you are looking for the ways to choose 1 element from each set. The number of ways to do this is the size of the set. Combinations problems usually involve choose k-many things from a set of n-many things, where k=1 or n is trivial.

Several methods of producing iterators in C# have been discussed here. (Including one by Jon Skeet).

If you are using .NET, you may also be interested in developed combinatorics modules, such as KwCombinatorics at CodePlex.

edit Now, with LINQ to the rescue:

private void cartesian1()
{
    textAppend("Cartesian 1");
    var setA = new[] { "whole wheat", "white", "rye" };
    var setB = new[] { "cold cut", "veggie", "turkey", "roast beef" };
    var setC = new[] { "everything", "just mayo" };

    var query =
        from bread in setA
        from meat in setB
        from toppings in setC
        let sandwich = String.Format("{1} on {0} with {2}",
            bread, meat, toppings)
        select sandwich;

    foreach( string sandwich in query )
    {
        textAppend(sandwich);
    }
}

---

A modified version of @Guffa's answer. I am by no means a creator of this code.

List<int> lists = new List<int> { 3, 2, 4 };

int[] cnt = new int[lists.Count];
int index;
do
{
    Console.WriteLine(String.Join(",", cnt));
    index = cnt.Length - 1;
    do
    {
        cnt[index] = (cnt[index] + 1) % lists[index];
    } while (cnt[index--] == 0 && index != -1);
} while (index != -1 || cnt[0] != 0);

Instead of using List<List<int>> - with possible values - use List<int> describing the amount of elements in collection. The output is the same an in original answer. The performance is better.