如何获得2D数组可能的组合
我有以下2D数组：
String[M][] String[0] "1","2","3" String[1] "A", "B" . . . String[M-1] "!" 所有可能的组合应存储在结果数组String[] combinations 。 例如：
combinations[0] == {"1A....!") combinations[1] == {"2A....!") combinations[2] == {"3A....!") combinations[3] == {"1B....!")
请注意，数组的长度可变。 输出String中元素的顺序无关紧要。 我也不在乎是否有重复。
如果数组长度相同，嵌套循环就可以了，但它们不是，我真的不知道如何解决这个问题。
您可以通过使用数组记录每个内部数组的大小，一次一个地迭代组合，以及一个计数器数组，用于跟踪每个内部数组使用哪个成员。 像这样的方法：
/** * Produce a List 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 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 combinationList = new ArrayList (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; }
该方法如何工作
如果你想象计数器数组就像一个数字时钟读数那么第一个String组合看到计数器数组全为零，所以第一个String是通过取每个内部数组的零元素（第一个成员）来产生的。
为了获得下一个组合，计数器数组增加1。 因此，最不重要的反指数增加1。 如果这导致其值变得等于它表示的内部数组的长度，那么索引被归零，并且下一个更重要的索引会增加。 单独的大小数组存储每个内部数组的长度，以便计数器数组循环知道索引何时达到其最大值。
例如，如果size数组是：
[3][3][2][1]
并且计数器arrays位于：
[0][2][1][0]
那么增量会使最不重要（最右边）的索引等于1，这是它的最大值。 因此，索引变为零，下一个更重要的索引（右起第二个）增加到2.但这也是该索引的最大值，因此它变为零，我们移动到下一个更重要的索引。 这会增加到3，这是它的最大值，因此它变为零，我们移动到最重要（最左边）的索引。 它增加到1，小于其最大值，因此递增的计数器数组变为：
[1][0][0][0]
这意味着下一个String组合是通过获取第一个内部数组的第二个成员和接下来的三个内部数组的第一个成员来实现的。
恐怖警告和笔记
我刚刚写了大约四十分钟，这是早上的一半，这意味着尽管它似乎完全符合要求，但很可能存在可以优化的错误或代码。 因此，如果性能至关重要，请务必对其进行彻底的unit testing。
请注意，它返回List而不是String数组，因为我认为Java Collections在大多数情况下比使用数组更受欢迎。 此外，如果您需要一个没有重复项的结果集，您只需将列表更改为一个Set，它将自动删除重复项并为您留下一个唯一的集。
如果您确实需要将结果作为String数组，请不要忘记您可以使用List方法将返回的List转换为您需要的。
这个问题有一个非常好的递归结构（这也意味着它可以在内存中爆炸，正确的方法应该使用迭代器，如另一个答案，但这个解决方案看起来更好，我们可以归纳certificate正确性因为递归性质）。 组合由第一个列表中的元素组成，该元素附加到由剩余（n-1）个列表组成的所有可能组合。 递归工作在AllCombinationsHelper中完成，但是您调用AllCombinations。 注意测试空列表和更广泛的。
public static List AllCombinations(List> aList) { if(aList.size() == 0) { return new ArrayList(); } List myFirstSubList = aList.remove(0); List myStrings = new ArrayList (); for(Character c : myFirstSubList) { myStrings.add(c.toString()); } return AllCombinationsHelper(aList, myStrings); } public static List AllCombinationsHelper(List> aList, List aCollection) { if(aList.size() == 0) { return aCollection; } List myFirstList = aList.remove(0); List myReturnSet = new ArrayList (); for(String s : aCollection) { for(Character c : myFirstList) { myReturnSet.add(c + s); } } return AllCombinationsHelper(aList, myReturnSet); }
应该直接用递归做。
让我重新说一下，所以术语不那么令人困惑。
我们将String []称为令牌列表，它是令牌列表
现在你有一个令牌列表列表，你想从每个令牌列表中获得一个令牌，并找出所有组合。
你需要做的是给出一个TokenList列表
- 如果List只有一个TokenList，则令牌列表本身的内容就是所有组合
- 否则，通过排除第一个令牌列表来创建子列表，并找出该子列表的所有组合。 当你有这些组合时，答案就是循环遍历你的第一个令牌列表，并使用令牌列表中的每个令牌和结果组合生成所有组合。
我只给了一个伪代码：
List allCombinations(List listOfTokenList) { if (length of strings == 1) { return strings[0]; } List subListCombinations = allCombination(listOfTokenList.subList(1)); // sublist from index 1 to the end List result; for each (token in listOfTokenList[0]) { for each (s in subListCombination) { result.add(token + s); } } return result; }
我一直在努力解决这个问题。 但我终于解决了它。 我的主要障碍是我用来声明每个变量的SCOPE。 如果未在正确的范围内声明变量，则变量将保留在上一次迭代中所做的更改。
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class RecursiveAlgorithmTest { private static int recursiveCallsCounter = 0; public static ArrayList> testCases = new ArrayList>(); /** * @param args the command line arguments */ public static void main(String[] args) { //set values for ArrayOfArrays ArrayList VariableA = new ArrayList (Arrays.asList("red", "green")); ArrayList VariableB = new ArrayList (Arrays.asList("A", "B", "C")); ArrayList VariableC = new ArrayList (Arrays.asList("1", "2", "3", "4")); ArrayList> AofA = new ArrayList>(); AofA.add(VariableA); AofA.add(VariableB); AofA.add(VariableC); System.out.println("Array of Arrays: ToString(): " +AofA.toString()); ArrayList optionsList = new ArrayList (); //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 newOptionsList, ArrayList> 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 currentAspectsOptions = newAofA.get(placeHolder); //iterate through the popped off options for (int i=0 ; i newOptions = new ArrayList (); //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 newTestCase = new ArrayList (); 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