Given an array of integers [x0 x1 x2], how do you calculate all possible permutations from [0 0 0] to [x0 x1 x2]?

Question

I am writing a program that takes in an ArrayList and I need to calculate all possible permutations starting with a list of zeroes, up to the value in the corresponding input list.

Does anyone know how to iteratively calculate these values?

For example, given [ 1 2 ] as input, it should find and store the following lists:

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

Thanks!

Answer 1

There is a useful link to Permutation generator

http://www.merriampark.com/perm.htm

This is a standard permutation problem. So this solution can be applied.

Answer 2

Here's a standard recursive generator:

import java.util.Arrays;

//...

static void generate(int... limits) {
    generate(new int[limits.length], limits, 0);
}
static void generate(int[] arr, int[] limits, int n) {
    if (n == limits.length) {
        System.out.println(Arrays.toString(arr));
    } else {
        for (int i = 0; i <= limits[n]; i++) {
            arr[n] = i;
            generate(arr, limits, n + 1);
        }
    }
}

//....

generate(1, 2);
/* prints
[0, 0]
[0, 1]
[0, 2]
[1, 0]
[1, 1]
[1, 2]
*/

This works in the same way as if you've had written variable number of nested loops. With recursion, you only have to write one loop, and it can actually have variable nesting depth (infinite if you're not careful!).

---

There's also the iterative i.e. non-recursive version:

static void generateI(int... limits) {
    int[] arr = new int[limits.length];
    int n;
    do {
        System.out.println(Arrays.toString(arr));
        n = limits.length - 1;
        while (n >= 0 && arr[n] == limits[n]) {
            arr[n] = 0;
            n--;
        }
        if (n >= 0) arr[n]++;
    } while (n >= 0);
}

This works in much the same way that increment by 1 works in binary arithmetic (or any base, really), except each position has its own limit.

For example, in base 10, here's how you increment:

 12399
     ^ (is highest digit, therefore set to 0, move left)

 12390
    ^ (is highest digit, therefore set to 0, move left)

 12400
   ^ (not the highest digit, add 1, DONE!)

Answer 3

It doesn't look like you actually want permutations. If you are given an array X = [1, 2], its permutations are exactly [1, 2] and [2, 1]. Going by your example, you want it to generate all tuples z where 0 <= z <= X.

This tuple-listing problem is nicely solved by polygenelubricants's solution. Your stated permutation problem is solved by Fazal's solution.