我如何循环遍历给定范围内的 N 个数字的排列，最好不使用递归？

Question

我有N 个数字和一个范围，我必须在该范围内对数字进行排列。例如，如果我有 3 个数字，范围为 1-2，我会循环1 1 1、1 1 2、1 2 1等。最好但不是必须的，我怎样才能在不递归的情况下做到这一点？对于一般想法，嵌套循环不允许任意数量的数字，并且由于深度太高，递归是不可取的（超过 1-10 的 3 个数字将超过 1,000 次调用使用这些数字的代码部分）

Answer 1

实现此目的的一种方法是每个排列循环一次迭代，并使用循环变量来计算排列所产生的值。考虑到范围的大小可以用作模参数来“截断”将成为结果中的值（数字）之一的值（数字）。然后，如果将循环变量（好吧，它的副本）除以范围大小，则重复上述操作以提取另一个值，...等。

显然，只有当结果数量不超过类型的容量int或用于循环变量的任何类型的容量时，这才有效。

所以看起来是这样的：

int [][] getResults(int numPositions, int low, int high) {

    int numValues = high - low + 1;

    int numResults = (int) Math.pow(numValues, numPositions);

    int results[][] = new int [numResults][numPositions];

    for (int i = 0; i < numResults; i++) {

        int result[] = results[i];

        int n = i;

        for (int j = numPositions-1; j >= 0; j--) {

            result[j] = low + n % numValues;

            n /= numValues;

        }

    }

    return results; 

}

您在问题中给出的示例将通过以下调用生成：

int results[][] = getResults(3, 1, 2);

那么结果是：

1 1 1

1 1 2

1 2 1

1 2 2

2 1 1

2 1 2

2 2 1

2 2 2