How to get a 2D array of possible combinations

Question

I have the following 2D array:

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

All possible combinations should be stored in the resulting String[] combinations array. For example:

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

Note that arrays are of variable length. The order of the elements in the output line does not matter. I also don't care if there are duplicates.

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

Answer 1

You can iterate through the combinations one at a time, for example, by the hour, using an array to record the size of each internal array and an array of counters that keeps track of which member to use from each internal 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 that an array of counters is like reading a digital clock, then the first combination of String sees an array of counters at all zeros, so the first line is created using the zero element (first element) of each internal array.

To get the next combination, the array of counters is incremented by one. Thus, the index of least significant counters increases by one. If this leads to the fact that its value becomes equal to the length of the internal array that it represents, then the index is zeroed, and the next index of greater significance increases. A separate dimensional array stores the length of each internal array, so the loop of the array counter knows when the index has reached its maximum.

For example, if an array of size:

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

and an array of counters:

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

then the increment will make the least significant (rightmost) index equal to 1, which is its maximum value. Thus, the index is zeroed, and the next index of greater significance (the second to the right of it) increases to 2. But this is also the maximum of this index, so it is zeroed and we move on to the next index of a larger value. This increases to three, which is its maximum value, so it is reset to zero and we move on to the most significant (left) index. This increases to 1, which is less than its maximum value, therefore the counter increases:

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

This means that the next String combination is performed using the second member of the first internal array and the first member of the next three internal arrays.

Warnings and style notes

I wrote it now in about forty minutes, and that’s half one in the morning, which means that even if he seems to be doing exactly what is needed, there are very likely errors or bits of code that could be optimized. Therefore, make sure that the unit test is complete if its performance is critical.

Note that it returns a List array, not a String array, because I think Java collections are much preferable to using arrays in most cases. In addition, if you need a result set without duplicates, you can simply change the list to a set that automatically removes duplicates and leaves you with a unique set.

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

Answer 2

This problem has a very good recursive structure (which also means that it can explode in memory, the correct way should be to use iterators like another answer, but this solution looks better, and we can prove the correctness inductively due to the recursive nature) . The combination consists of an element from the first list associated with all possible combinations formed from the remaining (n-1) lists. Recursive work is done in the AllCombinationsHelper, but you call AllCombinations. Note for checking empty lists and more broadly.

 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); } 

Answer 3

It should be directly related to recursion.

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

We will call String [] as a list of tokens, which is a list of tokens

Now you have a Token List, you want to get one token from each token list and find out all the combinations.

What you need to do, given the TokenList list

• If there is only one token list in the list, the contents of the token list itself are all combinations
• Otherwise, make a sub-list, excluding the first list of tokens and find out all the combinations of this subscription. When you have combinations, the answer simply goes through your first token list and generates all combinations using each token in the token list and result combinations.

I only give the 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; } 

Answer 4

I have been struggling with this problem for some time. But I finally decided it. My main hurdle is SCOPE, which I used to declare every variable. If you do not declare your variables in the correct scope, the variable will save the changes made in the previous iteration.

 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 

Answer 5

Python uses itertools.product and unpacking arguments (apply)

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