鉴于整数[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]，
[2：0]

[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屋！