Adding Elements From Each Row of Jagged Array

Question

I am trying to get every single combination of elements in a n-row, jagged 2d-array of strings by using only 1 element from each row.

An example array (With each line representing a row in the array):

"A","B","C"

"D","E"

"F","G","H","I","J"

For the above array there would be 30 possible combinations. Recursive solutions are welcome but I would prefer an iterative one for memory usage reasons.

Answer 1

Here's a fun little method using modulo:

public static void main(String args[]) {
    iterate(new String[][]{{"a","b","c"},{"d","e"},{"f","g","h","i"}});
}
static void iterate(String[][] jagged) {
    int count = 1;
    int[] divisors = new int[jagged.length];
    for (int j = 0; j < jagged.length; j++) {
        divisors[j] = count;
        count *= jagged[j].length;
    }
    for (int i = 0; i < count; i++) {
        String[] combination = new String[jagged.length];
        for (int j = 0; j < jagged.length; j++) {
            int mod = jagged[j].length;
            combination[j] = jagged[j][(i/divisors[j])%mod];
        }
        process(combination);
    }
}
static void process(String[] combination) {
    System.out.println(Arrays.toString(combination));
    // Do whatever you want here. Process as you go to save memory,
    // or add to a list to process later.
}

The heart of it is combination[j] = jagged[j][(i/divisors[j])%mod]; divisors[j] is the product of the earlier lengths, ie the number of combinations possible using the lower-indexed arrays. The mod is the length of the current array.

If you'd rather the last element iterate more quickly and the first more slowly, reverse the order when calculating divisors / count, that is, count j down from jagged.length to 0.

Answer 2

I can't think of any iterative solution to your problem if n is a variable.

The recursive solution:

ArrayList<String> permutations = new ArrayList<String>();
generatePermutations ("", 0);

/** Where the function generatePermutations is defined as: **/

void generatePermutations (String s, int index) {
    if (index >= n) {
        permutations.add(s);
        return;
    }
    for (String a : myJaggedArray[index]) {
        generatePermutations (s + a, index + 1)
    }
}

Answer 3

This should handle any size of a jagged array, but I only tested about 5 cases.

Our basic strategy is to use arrays to keep track of the current index of which element we will get next from the subarrays, and once we put a sequence into the permutationArray we will increase the rightmost index. If that index is equal to the size of the rightmost subarray, then we make the rightmost index 0 and increase the second-to-rightmost index. If that index is equal to the size of that subarray, we make that index 0 and increase the previous index. This process bubbles down to the first index until we have no more permutations left.

    char list[][] = new char[][] { { 'a', 'b', 'c' }, { 'd', 'e' },
            { 'f', 'g', 'h', 'i', 'j' } };

    int permutations = 1;
    for (int i = 0; i < list.length; ++i)
        permutations *= list[i].length;

    char permutationArray[][] = new char[permutations][list.length];

    // list of lengths of each subarray
    int listlength[] = new int[list.length];
    for (int i = 0; i < list.length; ++i)
        listlength[i] = list[i].length;

    // traverse list in a permutation, once this gets to the length then we
    // increase indicies starting from the right side
    int listindicies[] = new int[list.length];

    for (int i = 0; i < permutations; ++i) {
        for (int j = 0; j < list.length; ++j) {
            permutationArray[i][j] = list[j][listindicies[j]];

            if (j == (list.length - 1))
                listindicies[j]++;
        }

        // reset indicies if they are equal to the length of the array
        for (int k = list.length - 1; k >= 0; --k) {
            if (listindicies[k] == (listlength[k])) {
                listindicies[k] = 0;
                if (k != 0)
                    listindicies[k - 1]++;
            } else {
                break;
            }
        }

    }

    for (int i = 0; i < permutationArray.length; ++i) {
        for (int j = 0; j < permutationArray[i].length; ++j)
            System.out.print(permutationArray[i][j] + " ");
        System.out.println("");
    }