使用枚举器在C#中实现笛卡尔积

Question

使用枚举器在C#中实现笛卡尔积

3

我正在尝试实现在问题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

翻译：Results代表结果，12a为具体的数据。以上示例为重复出现的数据。

- Rob M

“it.Current” 中的 “it” 将始终是由 LINQ 语句 “from it in iterators” 新创建的，因此当然将始终返回第一个元素 - 顺便说一句：您可以仅使用 LINQ 和递归来完成所有这些操作 - 可能不太高效，但它将为您提供一个简单的第一次实现。 - Random Dev

谢谢！这个工作得非常好。 - Rob M

3个回答

1

@Carsten 提供了一份干净的代码，你可以尝试使用。如果你想修复你的代码，可以尝试像下面展示的那样将 yield return 投影出来。

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

- Siva Gopal

0

我过去使用的另一种Linq解决方案是使用Aggregate扩展。

将累加器初始化为空产品，每次循环时，我们通过将当前序列与到目前为止的产品组合来添加它。在每次迭代中，累加器将是到目前为止所有序列的笛卡尔积。

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

代码片段来源

- Mr. Bellis

1

你应该提及这段代码的来源。 - Thomas Levesque

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Random Dev · Accepted Answer

你代码中的问题

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

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