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

How to get 2D array possible combinations

提问by lekroif

I have the following 2D array:

我有以下二维数组：

String[M][]

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

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

All the possible combinations should be in store in a resulting array String[] combinations. So for example:

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

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

Notice that that the arrays are of variable length. Order of the elements in the output String doesn't matter. I also don't care if there are duplicates.

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

If the arrays were the same length, nested loops would do the trick, but they are not, and I really don't know how to approach the problem.

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

回答by Bobulous

You can iterate through the combinations one at a time like clockwork by using an array to record the size of each inner array, and a counter array which keeps track of which member to use from each inner array. Something like this method:

您可以通过使用一个数组来记录每个内部数组的大小，并使用一个计数器数组来跟踪每个内部数组中要使用的成员，从而像时钟一样一次迭代一个组合。像这样的方法：

/**
 * 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;
}

How the method works

该方法的工作原理

If you imagine the counter array being like a digital clock reading then the first String combination sees the counter array at all zeroes, so that the first String is made by taken the zero element (first member) of each inner array.

如果您将计数器数组想象成一个数字时钟读数，那么第一个字符串组合会看到计数器数组全部为零，因此第一个字符串是通过取每个内部数组的零元素（第一个成员）来制作的。

To get the next combination the counter array is incremented by one. So the least-significant counter index is increased by one. If this causes its value to become equal to the length of the inner array it represents then the index is zeroed, and the next index of greater significance is increased. A separate size array stores the length of each inner array, so that the counter array loop knows when an index has reached its maximum.

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

For example, if the size array was:

例如，如果大小数组是：

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

and the counter array was at:

计数器阵列位于：

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

then the increment would make the least significant (right-most) index equal to 1, which is its maximum value. So that index gets zeroed and the next index of greater significance (the second-from-right) gets increased to 2. But that is also the maximum of that index, so it gets zeroed and we move to the next index of greater significance. That gets increased to three, which is its maximum value so it gets zeroed and we move to the most significant (left-most) index. That gets increased to 1, which is less than its maximum so the incremented counter array becomes:

那么增量将使最不重要（最右边）的索引等于 1，这是它的最大值。所以该索引被清零，下一个更重要的索引（右起第二个）增加到 2。但这也是该索引的最大值，所以它被清零，我们移到下一个更重要的索引。它增加到三个，这是它的最大值，所以它被归零，我们移到最重要（最左边）的索引。它增加到 1，小于其最大值，因此递增的计数器数组变为：

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

Which means the next String combination is made by taking the second member of the first inner array, and the first member of the next three inner arrays.

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

Dire warnings and notes

可怕的警告和注意事项

I wrote this just now in about forty minutes, and it's half-one in the morning, which means that even though it seems to do exactly what is needed, there are very likely bugs or bits of code which could be optimised. So be sure to unit test it thoroughly if its performance is critical.

我刚刚在大约四十分钟内写了这个，现在是早上半点，这意味着即使它似乎完全按照需要执行，但很可能存在可以优化的错误或代码位。因此，如果其性能至关重要，请务必对其进行彻底的单元测试。

Note that it returns a List rather than a String array because I think that Java Collections are vastly preferable to using arrays in most cases. Also, if you need a result set with no duplicates, you can simply change the List to a Set which will automatically drop duplicates and leave you with a unique set.

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

If you really need the result as a String array, don't forget you can use the List<String>.toArray(String[])method to simply convert the returned List to what you need.

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

回答by Anil Vaitla

This problem has a very nice recursive structure to it (which also means it could explode in memory, the correct way should be using iterators such as the other answer, but this solution looks nicer imo and we can prove correctness inductively because of the recursive nature). A combination consists of an element from the first list attached to all possible combinations formed from the remaining (n-1) lists. The recursive work is done in AllCombinationsHelper, but you invoke AllCombinations. Note to test for empty lists and more extensively.

这个问题有一个非常好的递归结构（这也意味着它可能会在内存中爆炸，正确的方法应该是使用迭代器，比如另一个答案，但是这个解决方案看起来更好，我们可以归纳证明正确性，因为递归的性质）。组合由第一个列表中的元素组成，该元素附加到由剩余 (n-1) 个列表形成的所有可能组合。递归工作在 AllCombinationsHelper 中完成，但您调用 AllCombinations。注意测试空列表和更广泛的测试。

public static List<String> AllCombinations(List<List<Character>> aList) {
    if(aList.size() == 0) { return new ArrayList<String>(); }
    List<Character> myFirstSubList = aList.remove(0);
    List<String> myStrings = new ArrayList<String>();
    for(Character c : myFirstSubList) {
        myStrings.add(c.toString());
    }

    return AllCombinationsHelper(aList, myStrings);
}

public static List<String> AllCombinationsHelper(List<List<Character>> aList, 
                                                 List<String> aCollection) {
    if(aList.size() == 0) { return aCollection; }
    List<Character> myFirstList = aList.remove(0);
    List<String> myReturnSet = new ArrayList<String>();

    for(String s : aCollection) {
        for(Character c : myFirstList) {
            myReturnSet.add(c + s);
        }
    }

    return AllCombinationsHelper(aList, myReturnSet);
}

回答by Adrian Shum

Should be straight forward to do with recursion.

应该直接与递归有关。

Let me rephrase a bit, so the terminology is less confusing.

让我重新表述一下，这样术语就不会那么混乱了。

We will call String[] as Token List, which is a list of Tokens

我们将String[]称为Token List，它是一个Token列表

Now you have a List of Token List, you want to get one Token from each Token List available, and find out all combination.

现在你有一个令牌列表列表，你想从每个可用的令牌列表中获取一个令牌，并找出所有组合。

What you need to do is, given a list of TokenList

你需要做的是，给定一个 TokenList 列表

• If the List is having only one TokenList, the content of the Token List itself is all combinations
• Else, make a sub-list by excluding the first Token List, and find out all combinations of that sub list. When you have the combinations, the answer is simply loop through your first token list, and generate all combinations using each token in the token list, and the result combinations.

• 如果List只有一个TokenList，那么TokenList本身的内容就是所有的组合
• 否则，通过排除第一个令牌列表来制作子列表，并找出该子列表的所有组合。当你有组合时，答案是简单地循环你的第一个标记列表，并使用标记列表中的每个标记生成所有组合，以及结果组合。

I am only giving a psuedo code:

我只给出一个伪代码：

List<String> allCombinations(List<TokenList> listOfTokenList) {
  if (length of strings == 1) {
    return strings[0];
  }


  List<String> subListCombinations 
      = allCombination(listOfTokenList.subList(1));  // sublist from index 1 to the end


  List<String> result;
  for each (token in listOfTokenList[0]) {
    for each (s in subListCombination) {
      result.add(token + s);
    }
  }
  return result;
}

回答by JasonRobinson

I have been struggling with this problem for some time. But I finally solved it. My main obstacle was the SCOPE I used for declaring each variable. If you do not declare your variables in the correct scope, then the variable will retain changes made in the previous iteration.

我一直在努力解决这个问题。但我终于解决了。我的主要障碍是我用于声明每个变量的 SCOPE。如果您没有在正确的范围内声明您的变量，那么该变量将保留在前一次迭代中所做的更改。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class RecursiveAlgorithmTest {
    private static int recursiveCallsCounter = 0;
    public static ArrayList<ArrayList<String>> testCases = new ArrayList<ArrayList<String>>();

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        //set values for ArrayOfArrays
        ArrayList<String> VariableA = new ArrayList<String>(Arrays.asList("red", "green"));
        ArrayList<String> VariableB = new ArrayList<String>(Arrays.asList("A", "B", "C"));
        ArrayList<String> VariableC = new ArrayList<String>(Arrays.asList("1", "2", "3", "4"));

        ArrayList<ArrayList<String>> AofA = new ArrayList<ArrayList<String>>();
        AofA.add(VariableA); AofA.add(VariableB); AofA.add(VariableC);

        System.out.println("Array of Arrays: ToString(): " +AofA.toString());

        ArrayList<String> optionsList = new ArrayList<String>();

        //recursive call
        recurse(optionsList, AofA, 0);

        for (int i = 0 ; i < testCases.size() ; i++) {
            System.out.println("Test Case " + (i+1) + ": " + testCases.get(i));
            }

        }//end main(String args[])



    private static void recurse(ArrayList<String> newOptionsList, 
        ArrayList<ArrayList<String>> newAofA, int placeHolder){
        recursiveCallsCounter++;
        System.out.println("\n\tStart of Recursive Call: " + recursiveCallsCounter);
        System.out.println("\tOptionsList: " + newOptionsList.toString());
        System.out.println("\tAofA: " + newAofA.toString());
        System.out.println("\tPlaceHolder: "+ placeHolder);

        //check to see if we are at the end of all TestAspects
        if(placeHolder < newAofA.size()){

            //remove the first item in the ArrayOfArrays
            ArrayList<String> currentAspectsOptions = newAofA.get(placeHolder);
            //iterate through the popped off options




            for (int i=0 ; i<currentAspectsOptions.size();i++){
                ArrayList<String> newOptions = new ArrayList<String>();
                //add all the passed in options to the new object to pass on
                for (int j=0 ; j < newOptionsList.size();j++) {
                    newOptions.add(newOptionsList.get(j));
                }

                newOptions.add(currentAspectsOptions.get(i));
                int newPlaceHolder = placeHolder + 1;
                recurse(newOptions,newAofA, newPlaceHolder);
            }
        } else { // no more arrays to pop off
            ArrayList<String> newTestCase = new ArrayList<String>();
            for (int i=0; i < newOptionsList.size();i++){
                newTestCase.add(newOptionsList.get(i));
            }
            System.out.println("\t### Adding: "+newTestCase.toString());
            testCases.add(newTestCase);
        }
    }//end recursive helper 
}// end of test class

回答by Larry Stewart

In Python one uses itertools.product and argument unpacking (apply)

在 Python 中使用 itertools.product 和参数解包 (apply)

>>> import itertools
>>> S=[['1','2','3'],['A','B'],['!']]
>>> ["".join(x) for x in itertools.product(*S)]
['1A!', '1B!', '2A!', '2B!', '3A!', '3B!']