Algorithm for dynamic combinations

Question

Algorithm for dynamic combinations

My code has a list called INPUTS which contains dynamic number of lists, lets call them A, B, C, ... N. These lists contain dynamic number of events

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

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

I need to repeatedly call my function for each combination (the amount of input data is dynamic, in this example these are three parameters, 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've been thinking so far: So far, my approach is to create a list of combinations. The combination of elements is itself an "index" list for the input arrays A, B, and C. In our example:

my iCOMBINATIONS list 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 )
      {
           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 create a list of iCOMBINATIONS for any given number of INPUTS and their events. Any ideas?

Is there a better algorithm? any pseudo code that helps me would be great.

C # (or VB)

thanks

+2

c # algorithm combinations combinatorics

sOltan Apr 12 10:00 am

source to share

6 answers

Guffa · Answer 1 · 2010-04-12T06:39:54+0000

You can use an array to store the indices 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);

zsong · Answer 2 · 2010-04-12T06:18:03+0000

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

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

Marqus · Answer 3 · 2010-04-12T06:21:20+0000

I had a similar problem a while ago (generating combinations), I used the code from: http://www.merriampark.com/comb.htm . It's java, but I had no problem translating it to C #.

Luka Rahne · Answer 4 · 2010-04-12T06:46:01+0000

Put A, B, C in a 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)

maxwellb · Answer 5 · 2010-04-12T07:46:05+0000

It would seem that what you really want is neither a permutation nor a combination as such. You want to look at a Cartesian product (see here ) of multiple sets, iterating over which might involve iterating through combinations of individual sets.

However, this doesn't sound like a combination problem because you are looking for ways to select one item from each set. The number of ways to do this is the size of the set. Matching problems usually involve choosing k-many things from many n-many things, where k = 1 or n is trivial.

Several techniques for creating iterators in C # have been discussed here here . (Including one Jon Skeet).

If you are using .NET, you may also be interested in developed combinatorial modules like KwCombinatorics at CodePlex.

edit Now that 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);
    }
}

Alex · Answer 6 · 2018-03-16T09:01:15+0000

Modified version of @ Guffa's answer. I am in no way the 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 those List<int>

that describe the number of items in the collection. The result is similar to the original answer. Better performance.

Algorithm for dynamic combinations

More articles: