Wie man Listen mit verschiedenen Längen iteriert, um alle Permutationen zu finden?

Question

Dieser sollte nicht zu hart sein, aber mein Verstand scheint einen Stapelüberlauf (huehue) zu haben. Ich habe eine Reihe von Listen und ich möchte alle Permutationen finden, in denen sie bestellt werden können. Alle Listen haben unterschiedliche Längen.

Zum Beispiel:

Liste 1: 1

Liste 2: 1, 2

alle Permutationen wäre:

1, 1

1, 2

In meinem Fall vertausche ich die Zahlen nicht herum. (Zum Beispiel 2, 1) Was ist der einfachste Weg, dies zu schreiben?

Answer 1

Ich kann nicht sagen, ob die folgende ist der einfachste Weg, aber es ist IMO die effizienteste Art und Weise. Es ist im Grunde eine verallgemeinerte Version der meine Antwort auf die Looking at each combination in jagged array:

public static class Algorithms 
{ 
    public static IEnumerable<T[]> GenerateCombinations<T>(this IReadOnlyList<IReadOnlyList<T>> input) 
    { 
     var result = new T[input.Count]; 
     var indices = new int[input.Count]; 
     for (int pos = 0, index = 0; ;) 
     { 
      for (; pos < result.Length; pos++, index = 0) 
      { 
       indices[pos] = index; 
       result[pos] = input[pos][index]; 
      } 
      yield return result; 
      do 
      { 
       if (pos == 0) yield break; 
       index = indices[--pos] + 1; 
      } 
      while (index >= input[pos].Count); 
     } 
    } 
} 

Sie können die Erklärung in der verknüpften Antwort sehen (kurz es verschachtelte Schleifen Emulation). Auch da er aus Performancegründen den internen Puffer ohne Klonen erzeugt, müssen Sie ihn klonen, wenn Sie das Ergebnis für die spätere Verarbeitung speichern wollen.

Verwendungsbeispiel:

var list1 = new List<int> { 1 }; 
var list2 = new List<int> { 1, 2 }; 
var lists = new[] { list1, list2 }; 

// Non caching usage 
foreach (var combination in lists.GenerateCombinations()) 
{ 
    // do something with the combination 
} 

// Caching usage 
var combinations = lists.GenerateCombinations().Select(c => c.ToList()).ToList(); 

UPDATE: Die GenerateCombinations ist ein Standard-C# iterator Verfahren und die Implementierung emuliert grundsätzlich N verschachtelten Schleifen (wobei N ist die input.Count) wie folgt aus (in Pseudocode):

for (int i 0 = 0; i < Eingabe [0] .Zahl; i ++)
for (int i 1 = 0; i < Eingang [1] .Count; i ++)
for (int i 2 = 0; i < Eingang [2] .Count; i ++)
...
for (int i _N-1 = 0; i _N-1 < Eingang [N-1 ].Anzahl; i _N-1 ++)
Ausbeute {input [0] [i 0], input [1] [i ], input [2] [i 2], ..., Eingang [N-1] [i _N-1]}

oder es anders zeigt:

for (indices[0] = 0; indices[0] < input[0].Count; indices[0]++) 
{ 
    result[0] = input[0][indices[0]]; 
    for (indices[1] = 0; indices[1] < input[1].Count; indices[1]++) 
    { 
     result[1] = input[1][indices[1]]; 
     // ... 
     for (indices[N-1] = 0; indices[N-1] < input[N-1].Count; indices[N-1]++) 
     { 
      result[N-1] = input[N-1][indices[N-1]]; 
      yield return result; 
     } 
    } 
} 

Answer 2

Nested Loops:

List<int> listA = (whatever), listB = (whatever); 
var answers = new List<Tuple<int,int>>; 
for(int a in listA) 
    for(int b in listB) 
     answers.add(Tuple.create(a,b)); 
// do whatever with answers 

Answer 3

Try this:

Func<IEnumerable<string>, IEnumerable<string>> combine = null; 
combine = xs => 
    xs.Skip(1).Any() 
    ? xs.First().SelectMany(x => combine(xs.Skip(1)), (x, y) => String.Format("{0}{1}", x, y)) 
    : xs.First().Select(x => x.ToString()); 

var strings = new [] { "AB", "12", "$%" }; 

foreach (var x in combine(strings)) 
{ 
    Console.WriteLine(x); 
} 

Das gibt mir:

 
A1$ 
A1% 
A2$ 
A2% 
B1$ 
B1% 
B2$ 
B2%