vb.net - 在 vb.net 中查找列表值的所有组合(笛卡尔积)

Question

如何生成 N 个可变长度的 vb 列表中值的所有组合？

假设我有 N 个 vb 列表，例如

first = {'a', 'b', 'c', 'd'}
second = {'e'}
third =  {'f', 'g', 'h', 'i', 'j'}

(本例中为三个列表，但问题的列表数量为 N 个。)

我想输出它们值的所有组合，以生成一个列表列表的顺序。

{
{a,e,f}
{a,e,g}
{a,e,h}
{a,e,i}
{a,e,j}
{b,e,f}
{b,e,g}
....
{d,e,j}
}

Answer 1

简介

你想做的叫做:cartesian product

在继续之前，让我们做一些命名。我会将您的输入列表命名为 L_i其中 1 <= i <= n .我也会命名S_i输入列表的大小 L_i .

我们可以问这个问题:what is the size of the output ?

如果只有一个列表L_1 , 会有 S_1输出列表，每个列表只包含 L_1 的一个元素.

如果有两个列表{L_1, L_2} .对于 L_1 的每个元素我可以附加 S_2 L_2的不同元素.因为有S_1 L_1 的元素它使S_1*S_2不同的输出列表。

我们可以继续推理到n列出并证明输出列表的数量将为:S_1*...*S_n .

这对我们有什么帮助？因为我们现在可以创建一个数字 i 之间的映射和一个输出列表。

给定i一个数字 0<=i<S_1*...*S_n ，输出列表包含:

element of L_1 at index i/(S_2*S_3*...*S_n) MOD S_1
element of L_2 at index i/(    S_3*...*S_n) MOD S_2
...
element of L_n at index i                   MOD S_n

实现示例

我不了解 VB.net，所以我选择了使用相同 .net 平台的 C#。 我决定使用 yield return函数，这样我们就不会分配比需要更多的内存。如果您只需要打印输出，它只会消耗一个 ulong内存，而不是分配一个非常大的输出列表列表。

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

namespace cartesian_product
{
    class Program
    {
        public static IEnumerable<List<T>> cartesian_product<T>(IEnumerable<List<T>> lists)
        {
            ulong MAX_I = lists.Select(l => (ulong)l.Count)
                               .Aggregate(1ul, (a, b) => a * b);

            for (ulong i = 0; i < MAX_I; ++i)
            {
                var output = new List<T>();

                ulong div = MAX_I;
                ulong index, s_i;
                foreach (var l in lists)
                {
                    s_i    = (ulong)l.Count;
                    div   /= s_i;
                    index  = (i/div)%s_i;
                    output.Add(l[(int)index]);
                }
                yield return output;
            }
        }

        static void Main(string[] args)
        {
            var first = new List<Char> {'a', 'b', 'c', 'd'};
            var second = new List<Char> {'e'};
            var third = new List<Char> {'f', 'g', 'h', 'i', 'j'};

            Console.WriteLine("{");
            foreach (var output in cartesian_product(new[]{first, second, third}))
            {
                Console.WriteLine("{{{0}}}", string.Join(",", output));
            }
            Console.WriteLine("}");
        }
    }
}

输出是:

{
{a,e,f}
{a,e,g}
{a,e,h}
{a,e,i}
{a,e,j}
{b,e,f}
{b,e,g}
{b,e,h}
{b,e,i}
{b,e,j}
{c,e,f}
{c,e,g}
{c,e,h}
{c,e,i}
{c,e,j}
{d,e,f}
{d,e,g}
{d,e,h}
{d,e,i}
{d,e,j}
}

限制

有人可能会问:what if the product of the lists length overflows the variable used to index the outputs ? .

这是一个真正的理论问题，但我使用了 ulong在我的代码中，如果输出列表的总数溢出了这个变量，那么无论你使用什么方法，你都不可能枚举输出。 (因为理论输出将包含超过 2^64 个列表)。

应用程序

OP 没有解释他为什么首先需要这个算法。所以读者可能会想why is this useful ? .其中一个原因可能是为回归测试生成测试用例。假设您有一个将三个变量作为输入的遗留函数。您可以为每个参数生成一些可能的值，并使用笛卡尔积为每个可能的参数集收集函数的结果。重构遗留代码后，您可以通过比较新代码输出和遗留代码输出来确保没有回归。