给定一个整数数组 [x0 x1 x2]，你如何计算从 [0 0 0] 到 [x0 x1 x2] 的所有可能排列? [英] Given an array of integers [x0 x1 x2], how do you calculate all possible permutations from [0 0 0] to [x0 x1 x2]?

问题描述

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

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?

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

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]

[0 0], [1 0], [1 1], [1 2], [0 1], [0 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);
}

这与在二进制算术(或任何基数，实际上)中递增 1 的工作方式大致相同，只是每个位置都有自己的限制.

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.

例如，以 10 为基数，您的递增方式如下:

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!)

这篇关于给定一个整数数组 [x0 x1 x2]，你如何计算从 [0 0 0] 到 [x0 x1 x2] 的所有可能排列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！