Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to get 2D array possible combinations

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:

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.

like image 212
lekroif Avatar asked Apr 07 '13 23:04

lekroif


People also ask

How do you find the elements of a 2D array?

An element in 2-dimensional array is accessed by using the subscripts. That is, row index and column index of the array. int x = a[1,1]; Console.

What is the formula of 2D array?

The 2-Dimensional arrays are organized as matrices which can be represented as the collection of rows and columns as array[M][N] where M is the number of rows and N is the number of columns.

Can you have a 2D array with different types?

You can have multiple datatypes; String, double, int, and other object types within a single element of the arrray, ie objArray[0] can contain as many different data types as you need. Using a 2-D array has absolutely no affect on the output, but how the data is allocated.

How many elements are in a 2D array?

The number of elements in a 2D array is the number of rows times the number of columns.


3 Answers

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.

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);
}
like image 149
Anil Vaitla Avatar answered Oct 11 '22 05:10

Anil Vaitla


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][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.

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.

like image 36
Bobulous Avatar answered Oct 11 '22 06:10

Bobulous


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

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

  • 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.

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;
}
like image 25
Adrian Shum Avatar answered Oct 11 '22 06:10

Adrian Shum