使用枚举的C＃中的笛卡尔积

Question

我试图实现在问题中找到的解决方案之一C# Permutation of an array of arraylists? 它应该执行笛卡尔积，但是它会返回正确数量的列表，但每个列表总是只是每个阵列的第一个。代码和结果如下。

using System; 
using System.Collections; 
using System.Collections.Generic; 
using System.Linq; 

namespace TestCartProd 
{ 
    class MainClass 
    { 
     public static void Main (string[] args) 
     { 
      string[][] myList = new string[3][]; 
      myList[0] = new string[] { "1", "5", "3", "9" }; 
      myList[1] = new string[] { "2", "3" }; 
      myList[2] = new string[] { "a", "93" }; 

      List<IEnumerable<string>> v = GetPermutations (myList).ToList(); 

      foreach (IEnumerable t in v) { 
       foreach (string u in t) { 
        Console.Write (u); 
       } 
       Console.WriteLine(); 
      } 

     } 

     public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<IEnumerable<T>> lists) 
     { 
      // Check against an empty list. 
      if (!lists.Any()) 
      { 
       yield break; 
      } 

      // Create a list of iterators into each of the sub-lists. 
      List<IEnumerator<T>> iterators = new List<IEnumerator<T>>(); 
      foreach (var list in lists) 
      { 
       var it = list.GetEnumerator(); 
       // Ensure empty sub-lists are excluded. 
       if (!it.MoveNext()) 
       { 
        continue; 
       } 
       iterators.Add(it); 
      } 

      bool done = false; 
      while (!done) 
      { 
       // Return the current state of all the iterator, this permutation. 
       yield return from it in iterators select it.Current; 

       // Move to the next permutation. 
       bool recurse = false; 
       var mainIt = iterators.GetEnumerator(); 
       mainIt.MoveNext(); // Move to the first, succeeds; the main list is not empty. 
       do 
       { 
        recurse = false; 
        var subIt = mainIt.Current; 
        if (!subIt.MoveNext()) 
        { 
         subIt.Reset(); // Note the sub-list must be a reset-able IEnumerable! 
         subIt.MoveNext(); // Move to the first, succeeds; each sub-list is not empty. 

         if (!mainIt.MoveNext()) 
         { 
          done = true; 
         } 
         else 
         { 
          recurse = true; 
         } 
        } 
       } 
       while (recurse); 
      } 
     } 
    } 
} 

结果： 12A 12A 12A 12A 12A 12A 12A 12A 12A 12A 12A 12A 12A 12A 12A 12A

Answer 1

在你的代码的问题

的it在it.Current总会被新创建（由LINQ声明：from it in iterators）等，当然起初总是返回的第一要素

LINQ解决方案

我不会看太多的性能并且使用简单的LINQ /递归实现算法 - 下面是一个例子（我明明使用的一些列表类似的术语与可枚举，并没有在意性能，堆栈使用......在所有）：

public static IEnumerable<T> Empty<T>() 
{ 
    return new T[] {}; 
} 

public static IEnumerable<T> Cons<T>(T head, IEnumerable<T> tail) 
{ 
    yield return head; 
    foreach (var t in tail) 
     yield return t; 
} 
public static IEnumerable<IEnumerable<T>> Crossproduct<T>(IEnumerable<IEnumerable<T>> sets) 
{ 
    if (!sets.Any()) 
     return new[] {Empty<T>()}; 

    var head = sets.First(); 
    var tailCross = Crossproduct<T>(sets.Skip(1)); 

    return 
     from h in head 
     from ts in tailCross 
     select Cons(h, ts); 
} 

从这里开始y如果你愿意的话，你可以开始将它翻译回来，但正如你在例子中看到的那样，这并不容易。

言论

当你看到我做不修复你的代码（你应该能够使用调试自己做），但你没有问任何问题，这一切可能会感兴趣与否。

例如输出

使用你提供的例子，输出回路与此代码：

string[][] myList = new string[3][]; 
myList[0] = new string[] { "1", "5", "3", "9" }; 
myList[1] = new string[] { "2", "3" }; 
myList[2] = new string[] { "a", "93" }; 

var crossP = Crossproduct(myList); 

foreach (var t in crossP) 
{ 
    foreach (string u in t) 
    { 
     Console.Write(u); 
    } 
    Console.WriteLine(); 
} 

产生这个（我认为这是你想要的）：

12a 
1293 
13a 
1393 
52a 
5293 
53a 
5393 
32a 
3293 
33a 
3393 
92a 
9293 
93a 
9393 

Answer 2

@ Carsten提供了一个干净的代码，您可以尝试。但如果你想修复你的代码，你可以尝试投射产量收益如下图所示：

while (!done) 
      { 
       // Return the current state of all the iterator, this permutation. 
       yield return iterators.Select(it => it.Current).ToArray(); 
       //Notice Select(...).ToArray() above. 

Answer 3

我已经在过去使用的另一种Linq的解决方案是使用总结推广。

将我们的蓄​​能器作为空产品启动，并且每次通过我们添加的循环时，通过将当前序列与产品结合到目前为止。在每一次迭代中，累加器将是迄今为止所看到的所有序列的笛卡尔乘积。

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) 
{ 
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
    return sequences.Aggregate(
    emptyProduct, 
    (accumulator, sequence) => 
     from accseq in accumulator 
     from item in sequence 
     select accseq.Concat(new[] {item})); 
} 

Code Snippet Source