时间戳

首页 > 解决方案 > 我将如何遍历具有给定范围的 N 个数字的排列，最好不使用递归？

java - 我将如何遍历具有给定范围的 N 个数字的排列，最好不使用递归？

问题描述

我有N个数字和一个范围，我必须在这个范围内排列这些数字。

例如，如果我有 3 个数字和 1-2 的范围，我会循环1 1 1, 1 1 2,1 2 1等。

最好但不一定，如果没有递归，我怎么能做到这一点？

对于一般的想法，嵌套循环不允许任意数量的数字，并且由于深度高，递归是不可取的（超过 1-10 的 3 个数字将超过 1,000 次使用这些数字的代码段调用）

标签： javaalgorithmpermutation

解决方案

做到这一点的一种方法是，每次置换循环一次，并使用循环变量来计算置换产生的值。考虑到范围的大小可以用作模参数来“截断”一个值（数字），该值将是结果中的值（数字）之一。然后，如果您将循环变量（好吧，它的副本）除以范围大小，则重复上述操作以提取另一个值，...等等。

显然，这仅在结果数量不超过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

推荐阅读