Generating All Permutations of Character Combinations when # of arrays and length of each array are unknown

arraylist, arrays, computer-science, multidimensional-array, permutation

Solution

Recursive solution

This is actually the easiest, most straightforward solution. The following is in Java, but it should be instructive:

public class Main {
    public static void main(String[] args) {
        Object[][] arrs = {
            { "X", "Y", "Z" },
            { "A", "B" },
            { "1", "2" },
        };
        recurse("", arrs, 0);
    }
    static void recurse (String s, Object[][] arrs, int k) {
        if (k == arrs.length) {
            System.out.println(s);
        } else {
            for (Object o : arrs[k]) {
                recurse(s + o, arrs, k + 1);
            }
        }
    }
}

(see full output)

Note: Java arrays are 0-based, so `k` goes from `0..arrs.length-1` during the recursion, until `k == arrs.length` when it's the end of recursion.

Non-recursive solution

It's also possible to write a non-recursive solution, but frankly this is less intuitive. This is actually very similar to base conversion, e.g. from decimal to hexadecimal; it's a generalized form where each position have their own set of values.

public class Main {
    public static void main(String[] args) {
        Object[][] arrs = {
            { "X", "Y", "Z" },
            { "A", "B" },
            { "1", "2" },
        };
        int N = 1;
        for (Object[] arr : arrs) {
            N = N * arr.length;
        }
        for (int v = 0; v < N; v++) {
            System.out.println(decode(arrs, v));
        }
    }
    static String decode(Object[][] arrs, int v) {
        String s = "";
        for (Object[] arr : arrs) {
            int M = arr.length;
            s = s + arr[v % M];
            v = v / M;
        }
        return s;
    }
}

(see full output)

This produces the tuplets in a different order. If you want to generate them in the same order as the recursive solution, then you iterate through `arrs` "backward" during `decode` as follows:

static String decode(Object[][] arrs, int v) {
    String s = "";
    for (int i = arrs.length - 1; i >= 0; i--) {
        int Ni = arrs[i].length;
        s = arrs[i][v % Ni] + s;
        v = v / Ni;
    }
    return s;
}

(see full output)

Problem

I'm not sure how to ask my question in a succinct way, so I'll start with examples and expand from there. I am working with VBA, but I think this problem is non language specific and would only require a bright mind that can provide a pseudo code framework. Thanks in advance for the help! Example: I have 3 Character Arrays Like So: ``` Arr_1 = [X,Y,Z] Arr_2 = [A,B] Arr_3 = [1,2,3,4] ``` I would like to generate ALL possible permutations of the character arrays like so: ``` XA1 XA2 XA3 XA4 XB1 XB2 XB3 XB4 YA1 YA2 . . . ZB3 ZB4 ``` This can be easily solved using 3 while loops or for loops. My question is how do I solve for this if the # of arrays is unknown and the length of each array is unknown? So as an example with 4 character arrays: ``` Arr_1 = [X,Y,Z] Arr_2 = [A,B] Arr_3 = [1,2,3,4] Arr_4 = [a,b] ``` I would need to generate: ``` XA1a XA1b XA2a XA2b XA3a XA3b XA4a XA4b . . . ZB4a ZB4b ``` So the Generalized Example would be: ``` Arr_1 = [...] Arr_2 = [...] Arr_3 = [...] . . . Arr_x = [...] ``` Is there a way to structure a function that will generate an unknown number of loops and loop through the length of each array to generate the permutations? Or maybe there's a better way to think about the problem? Thanks Everyone!

Original source