java - 如何获得二维数组可能的组合

Question

我有以下二维数组:

String[M][]

String[0]
   "1","2","3"

String[1]
   "A", "B"
   .
   .
   .
String[M-1]
   "!"

所有可能的组合都应该存储在结果数组中String[] 组合。例如:

combinations[0] == {"1A....!")
combinations[1] == {"2A....!") 
combinations[2] == {"3A....!") 
combinations[3] == {"1B....!")

请注意，数组的长度是可变的。输出字符串中元素的顺序无关紧要。我也不在乎是否有重复。

如果数组长度相同，嵌套循环就可以解决问题，但事实并非如此，我真的不知道如何解决这个问题。

Answer 1

您可以像发条一样一次迭代组合，方法是使用一个数组来记录每个内部数组的大小，并使用一个计数器数组来跟踪每个内部数组中要使用的成员。像这样的方法:

/**
 * Produce a List<String> which contains every combination which can be
 * made by taking one String from each inner String array within the
 * provided two-dimensional String array.
 * @param twoDimStringArray a two-dimensional String array which contains
 * String arrays of variable length.
 * @return a List which contains every String which can be formed by taking
 * one String from each String array within the specified two-dimensional
 * array.
 */
public static List<String> combinations(String[][] twoDimStringArray) {
    // keep track of the size of each inner String array
    int sizeArray[] = new int[twoDimStringArray.length];

    // keep track of the index of each inner String array which will be used
    // to make the next combination
    int counterArray[] = new int[twoDimStringArray.length];

    // Discover the size of each inner array and populate sizeArray.
    // Also calculate the total number of combinations possible using the
    // inner String array sizes.
    int totalCombinationCount = 1;
    for(int i = 0; i < twoDimStringArray.length; ++i) {
        sizeArray[i] = twoDimStringArray[i].length;
        totalCombinationCount *= twoDimStringArray[i].length;
    }

    // Store the combinations in a List of String objects
    List<String> combinationList = new ArrayList<String>(totalCombinationCount);

    StringBuilder sb;  // more efficient than String for concatenation

    for (int countdown = totalCombinationCount; countdown > 0; --countdown) {
        // Run through the inner arrays, grabbing the member from the index
        // specified by the counterArray for each inner array, and build a
        // combination string.
        sb = new StringBuilder();
        for(int i = 0; i < twoDimStringArray.length; ++i) {
            sb.append(twoDimStringArray[i][counterArray[i]]);
        }
        combinationList.add(sb.toString());  // add new combination to list

        // Now we need to increment the counterArray so that the next
        // combination is taken on the next iteration of this loop.
        for(int incIndex = twoDimStringArray.length - 1; incIndex >= 0; --incIndex) {
            if(counterArray[incIndex] + 1 < sizeArray[incIndex]) {
                ++counterArray[incIndex];
                // None of the indices of higher significance need to be
                // incremented, so jump out of this for loop at this point.
                break;
            }
            // The index at this position is at its max value, so zero it
            // and continue this loop to increment the index which is more
            // significant than this one.
            counterArray[incIndex] = 0;
        }
    }
    return combinationList;
}

该方法的工作原理

如果您将计数器数组想象成数字时钟读数，那么第一个字符串组合会看到计数器数组全为零，因此第一个字符串是由每个内部数组的零元素(第一个成员)组成的。

为了获得下一个组合，计数器数组递增 1。因此，最不重要的计数器索引增加 1。如果这导致它的值变得等于它所代表的内部数组的长度，那么该索引将被清零，并且增加下一个更重要的索引。一个单独的大小数组存储每个内部数组的长度，以便计数器数组循环知道索引何时达到其最大值。

例如，如果大小数组是:

[3][3][2][1]

计数器数组位于:

[0][2][1][0]

然后增量将使最不重要(最右边)的索引等于 1，这是它的最大值。因此该索引归零，下一个更重要的索引(右数第二个)增加到 2。但这也是该索引的最大值，所以它被归零，我们移动到下一个更重要的索引。它增加到 3，这是它的最大值，所以它被清零，我们移动到最重要(最左边)的索引。它增加到 1，小于它的最大值，因此递增的计数器数组变为:

[1][0][0][0]

这意味着下一个字符串组合是通过获取第一个内部数组的第二个成员和接下来的三个内部数组的第一个成员组成的。

可怕的警告和注意事项

我刚刚写了大约四十分钟，现在是凌晨一点半，这意味着即使它看起来完全符合需要，但很可能存在错误或可以优化的代码位。因此，如果其性能至关重要，请务必对其进行彻底的单元测试。

请注意，它返回一个列表而不是一个字符串数组，因为我认为在大多数情况下 Java 集合比使用数组更可取。此外，如果您需要一个没有重复项的结果集，您只需将列表更改为一个集合，它会自动删除重复项并为您留下一个唯一的集合。

如果您确实需要字符串数组形式的结果，请不要忘记您可以使用 List<String>.toArray(String[])方法简单地将返回的列表转换为您需要的内容。