java - Combinatorics: generate all "states" - array combinations

Question

I have an array of integers: n[].

Also, I have an array (Nr[]) contains n.length integers. I need to generate all combinations of n[] in a following way:

/* let n.length == 3 and Nr[0] = 2, Nr[1] = 3, Nr[2] = 3 */
n = {0, 0, 0};
n = {1, 0, 0};
n = {2, 0, 0};
n = {0, 1, 0};
n = {0, 2, 0};
n = {0, 3, 0};
n = {0, 0, 1};
...
n = {1, 1, 0};
n = {1, 2, 0};
n = {1, 3, 0};
n = {2, 1, 0};
n = {2, 2, 0};
n = {2, 3, 0};
n = {1, 1, 1};
...
n = {0, 1, 1};
// many others

The goal is to find all combinations of n, where n[i] can be 0 to Nr[i].

I did not succeed... How to solve it in Java? Or not in Java...

Answer 1

You might want to use recursion, try all possibilities for each index, and recursively invoke with the subarray, "without" the last element.

public static void printPermutations(int[] n, int[] Nr, int idx) {
    if (idx == n.length) {  //stop condition for the recursion [base clause]
        System.out.println(Arrays.toString(n));
        return;
    }
    for (int i = 0; i <= Nr[idx]; i++) { 
        n[idx] = i;
        printPermutations(n, Nr, idx+1); //recursive invokation, for next elements
    }
}

invoke with:

public static void main(String[] args) {
    /* let n.length == 3 and Nr[0] = 2, Nr[1] = 3, Nr[2] = 3 */
    int[] n = new int[3];
    int Nr[] = {2,3,3 };
    printPermutations(n, Nr, 0);
}

will get you:

[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 0, 3]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
[0, 1, 3]
[0, 2, 0]
[0, 2, 1]
[0, 2, 2]
[0, 2, 3]
[0, 3, 0]
[0, 3, 1]
[0, 3, 2]
[0, 3, 3]
[1, 0, 0]
[1, 0, 1]
[1, 0, 2]
[1, 0, 3]
[1, 1, 0]
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 2, 0]
[1, 2, 1]
[1, 2, 2]
[1, 2, 3]
[1, 3, 0]
[1, 3, 1]
[1, 3, 2]
[1, 3, 3]
[2, 0, 0]
[2, 0, 1]
[2, 0, 2]
[2, 0, 3]
[2, 1, 0]
[2, 1, 1]
[2, 1, 2]
[2, 1, 3]
[2, 2, 0]
[2, 2, 1]
[2, 2, 2]
[2, 2, 3]
[2, 3, 0]
[2, 3, 1]
[2, 3, 2]
[2, 3, 3]

Note however - that using this method does print all elements as you describes, but in a different order then your example.