[Solved] Iterate through every permutation of an array of numbers

by


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.

1

solved Iterate through every permutation of an array of numbers