algorithme pour les combinaisons dynamiques

Question

Mon code a une liste appelée ENTREES, qui contient un nombre dynamique de listes, nous allons les appeler A, B, C, .. N. Ces listes contiennent un nombre dynamique des événements

Je voudrais aime appeler une fonction avec chaque combinaison d'événements. Pour illustrer par un exemple:

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

Je dois appeler ma fonction de nombreuses reprises pour chaque combinaison (le nombre d'entrée est dynamique, dans cet exemple, il est de trois paramètres, mais il peut être plus ou moins)

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]) 

C'est ce à quoi j'ai pensé jusqu'à présent: Mon approche jusqu'à présent consiste à construire une liste de combinaisons. La combinaison d'élément lui-même est une liste de « index » aux tableaux d'entrée A, B et C. Pour notre exemple:

ma liste iCOMBINATIONS contient les listes iCOMBO suivantes

(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) 

Alors je faire ceci:

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) 
     } 
} 

Mais je dois trouver un moyen de construire la liste iCOMBINATIONS pour un nombre donné de ENTRÉES et leurs événements. Des idées?

Existe-t-il réellement un meilleur algorithme que celui-ci? tout pseudo code pour m'aider sera super.

C# (ou VB)

Merci Vous

Answer 1

Ce problème est de permutation. Vous pouvez jeter un oeil à ceci:

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

Answer 2

J'ai eu le même problème il y a quelque temps (générant des combinaisons), je l'ai utilisé le code de: http://www.merriampark.com/comb.htm. C'est java, mais je n'ai eu aucun problème pour le traduire en C#.

Answer 3

Vous pouvez utiliser un tableau pour stocker les index de chaque liste. Exemple:

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); 

Answer 4

Put A, B, C dans la matrice! 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) 

Answer 5

Il semblerait que ce que vous avez vraiment voulez, est ni une permutation, ni une combinaison, en tant que tel. Vous voulez regarder le cartesian product (voir here) de plusieurs ensembles, l'itération sur laquelle peut impliquer itération à travers des combinaisons d'ensembles individuels. Cependant, cela ne ressemble pas à un problème de combinaison, car vous cherchez des façons de choisir 1 élément dans chaque ensemble. Le nombre de façons de le faire est la taille de l'ensemble. Combinaisons problèmes impliquent généralement choisir k choses -Beaucoup d'un ensemble de n choses -Beaucoup, où k = 1 ou n est trivial.

Plusieurs méthodes de production d'itérateurs en C# ont été discutées here. (Y compris un par Jon Skeet).

Si vous utilisez .NET, vous pouvez également être intéressé par des modules combinatoires développés, tels que KwCombinatorics sur CodePlex.

modifier Maintenant, avec LINQ à la rescousse:

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); 
    } 
}