给定一个整数数组 [x0 x1 x2]，如何计算从 [0 0 0] 到 [x0 x1 x2] 的所有可能排列？

Question

我正在编写一个接受 ArrayList 的程序，我需要计算所有可能的排列，从零列表开始，直到相应输入列表中的值。

有谁知道如何迭代计算这些值？

例如，给定 [ 1 2 ] 作为输入，它应该查找并存储以下列表：

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

谢谢！

Answer 1

这是一个标准的递归生成器：

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]
*/

它的工作方式与编写可变数量的嵌套循环相同。使用递归，您只需要编写一个循环，并且它实际上可以具有可变的嵌套深度（如果您不小心，则可以是无限的！）。

---

还有迭代即非递归版本：

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);
}

这与二进制算术（或任何基数，实际上）中加 1 的工作方式大致相同，只是每个位置都有其自己的限制。

例如，以 10 为基数，递增方式如下：

 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 2

看起来您实际上并不想要排列。如果给定一个数组 X = [1, 2]，它的排列恰好是 [1, 2] 和 [2, 1]。根据您的示例，您希望它生成所有元组 z，其中 0 <= z <= X。polygenelubricants

的解决方案很好地解决了这个元组列表问题。 Fazal 的解决方案解决了您所说的排列问题。