Iterate through every permutation of an array of numbers

Question

My problem is such: I have n amount of numbers in an array, each with a maximum value m, and I would like to iterate through every permutation of these numbers, by incrementing them individually until they reach their maximum.

An example:

[0,0,0,0]

Integer @ index 0 has a max value of 5
Integer @ index 1 has a max value of 3
Integer @ index 2 has a max value of 4
Integer @ index 3 has a max value of 6

Output: 
[0,0,0,1]
[0,0,0,2]
[0,0,0,3]
.
.
.
[0,1,1,0]
[0,1,1,1]
[0,1,1,2]
[0,1,1,3]
.
.
.
[5,0,2,1]
[5,0,2,2]
etc.

Python has itertools with the product function, which would solve my problem, but it does not look like Java has something similar. Recursion seem to be the way to go but I can figure out the way forward.

Does anyone know how to achieve above mentioned output? Thanks in advance :-)

I've tried Googling but the solutions i've found do not include duplicates and only create permutations of a set of numbers. But thanks for referring me to Google, very helpful. — 2wave, Oct 30 '19 at 18:35
Welcome to stackoverflow.com. Please take some time to read [the help pages](http://stackoverflow.com/help), also please [take the tour](http://stackoverflow.com/tour) and read about [how to ask good questions](http://stackoverflow.com/help/how-to-ask). Finally please read this [question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/) — Curiosa Globunznik, Oct 30 '19 at 18:36
Possible duplicate of [Generating all permutations of a given string](https://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string) — Curiosa Globunznik, Oct 30 '19 at 18:49

score 0 · Accepted Answer · answered Oct 30 '19 at 18:43

Technically, a permutation means a re-ordering of some elements, so for example, [3,1,2] is a permutation of [1,2,3]. What you're asking for is equivalent to iterating over a Cartesian product, hence the Python function being named product.

As you correctly note, recursion is the way to go here. This is because generating all sequences for [5,3,4,6] requires generating all sequences for [3,4,6] with 0 at the start, then again with 1 at the start, and so on up to 5.

import java.util.Arrays;

public class CartesianProduct {
    public static void main(String[] args) {
        printAll(5, 3, 4, 6);
    }

    public static void printAll(int... maxes) {
        int[] current = new int[maxes.length];
        printAll(maxes, current, 0);
    }

    private static void printAll(int[] maxes, int[] current, int i) {
        if(i == current.length) {
            System.out.println(Arrays.toString(current));
        } else {
            int max = maxes[i];
            for(int j = 0; j <= max; ++j) {
                current[i] = j;
                printAll(maxes, current, i+1);
            }
        }
    }
}

The variable i is the index of the place we're currently choosing a value for, the variable j is the current value in that place, and the array current holds the current sequence. The base case for the recursion is when values have been chosen in all places, so then we print.

Thank you very much! Knowing it's cartesian products and not permutation is great. You've been a big help, and thanks for the code too :-) — 2wave, Oct 30 '19 at 21:52

Iterate through every permutation of an array of numbers

1 Answers1