迭代数字数组的每个排列

Question

我的问题是这样的：我在一个数组中有 n 个数字，每个数字都有一个最大值 m，我想通过单独递增它们直到达到最大值来迭代这些数字的每个排列。一个例子：[0,0,0,0]Integer @ index 0 has a max value of 5Integer @ index 1 has a max value of 3Integer @ index 2 has a max value of 4Integer @ index 3 has a max value of 6Output: [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有带有product函数的itertools，这可以解决我的问题，但看起来Java没有类似的东西。递归似乎是可行的方法，但我可以找出前进的方向。有谁知道如何实现上述输出？提前致谢 ：-）

Answer 1

从技术上讲，排列意味着某些元素的重新排序，例如，[3,1,2]是 的排列[1,2,3]。您所要求的相当于迭代笛卡尔积，因此 Python 函数被命名为product。

---

正如您正确地注意到的，递归是这里的方法。这是因为生成 的所有序列[5,3,4,6]需要生成[3,4,6]以 0 开头的所有序列，然后再次以 1 开头，依此类推，直到 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);

            }

        }

    }

}

变量i是我们当前选择值的位置的索引，变量j是该位置的当前值，数组current保存当前序列。递归的基本情况是在所有位置都选择了值，然后我们打印。