arrays - 如何找到多个数组项的所有组合

Question

假设这些是起始数组：

[a,b,c]
[d]
[e,f]

什么算法可以产生以下数组？

[a,d,e]
[a,d,f]
[b,d,e]
[b,d,f]
[c,d,e]
[c,d,f]

起始数组的数量可以变化。

Answer 1

取决于语言，但形式上是这样的（当您指定 3 个数组时）

for el1 in first_array do
  for el2 in second_array do
    for el3 in third_array do
      begin
        create new element in result array as [e1, el2, el3]
      end

Answer 2

假设有 k 个数组，分别包含 n ₁、 n ₂ ... n _k个元素。
写所有组合很像用混合基数写所有数字。
因此，只需遍历从 0 到 (n ₁ n ₂ ...n _k -1) 的所有可能数字，并用从数组中获取的“数字”以混合基数表示形式将其写下来 - 只需要两个嵌套循环。

Answer 3

你能想到的最简单的算法就是你能拥有的最好的算法。由于答案是大小，因此所有数组的乘法维度在这里并没有太大的改进。我个人建议使用递归，因为数组的数量不能太大，而不会使结果数组的数量非常大。

Answer 4

另一种方法是图形方法，您从原始集开始，顺时针移动它们的内容并存储组合。示例首先旋转最后一行，最后一次旋转后移动最后 - 1 行（在本例中为 d，但您不能旋转它），因此您将旋转第一行。这就像二进制和。

[a,b,c]     [a,b,c]---->[b,c,a]     [b,c,a]---->[c,a,b]     [c,a,b]              
[d]         [d]         [d]         [d]         [d]         [d]    
[e,f]------>[f,e]------>[e,f]------>[f,e]------>[e,f]------>[f,e]

PD：你只会保存每个数组的第一个元素。

Answer 5

上面提出的解决方案有一个很大的问题，开发人员需要知道前面的数组数量并相应地创建循环的数量。

C# 中的以下解决方案根据您实际拥有的数组数量动态执行它，并且它与类型无关：

    static void Main(string[] args)
    {
        List<List<char>> masterListChar = new List<List<char>>();
        List<char> c1 = new List<char>() { 'a', 'b', 'c' };
        List<char> c2 = new List<char>() { 'd' };
        List<char> c3 = new List<char>() { 'e', 'f'};
        masterListChar.Add(c1);
        masterListChar.Add(c2);
        masterListChar.Add(c3);

        //PrintCombinations(masterListInt);
        PrintCombinations(masterListChar);
        Console.ReadKey();
    }

    public static void PrintCombinations<T>(List<List<T>> masterArray)
    {
        T[] combination = new T[masterArray.Count];
        WalkOnSubArray(combination, masterArray, 0);
    }

    public static void WalkOnSubArray<T>(T[] combination, List<List<T>> masterArray, int masterIndex)
    {
        List<T> currentArray = masterArray[masterIndex];
        for (int i = 0; i < currentArray.Count; ++i)
        {
            combination[masterIndex] = currentArray[i];

            if(masterIndex != masterArray.Count - 1)
                WalkOnSubArray(combination, masterArray, masterIndex + 1);
            else
                Console.WriteLine(String.Join(",", combination));
        }
    }