c# - 使用枚举的 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.Current 中的 it 总是新创建的(通过 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);
}

如果您愿意，您可以从这里开始将其翻译回循环，但正如您在示例中看到的那样，这并不容易。

备注

如您所见，我没有修复您的代码(您应该可以使用调试器自己完成此操作)，但由于您确实没有提出任何问题，所以这可能是有趣的，也可能不是。

示例输出

使用您提供的示例和带有此代码的输出循环:

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