给定一个由元素数组表示的排列，是否可以有效地计算第 n 个排列，而无需计算其间的每个排列？
答案在于阶乘分解。考虑排列的字典顺序。通过将排列的索引分解为阶乘分数，我们可以推导出具体的排列。
这种方法允许我们直接跳转到所需的排列，而不需要强力迭代。
例如，给定一个数组 {A, B, C}，大小为 2 的第三个排列的阶乘分解将为 (2! * 0) (1! * 1) = (2 * 0) (1 * 1) = 1。这对应于第 1 个元素 (B)，后跟第 0 个元素 (A)。
以下 C 实现演示了此技术：
void ithPermutation(const int n, int i) {
int *fact = (int *)calloc(n, sizeof(int));
int *perm = (int *)calloc(n, sizeof(int));
// Compute factorial numbers
fact[0] = 1;
for (int k = 1; k < n; k++) {
fact[k] = fact[k - 1] * k;
}
// Compute factorial code
for (int k = 0; k < n; k++) {
perm[k] = i / fact[n - 1 - k];
i = i % fact[n - 1 - k];
}
// Readjust values to obtain the permutation
for (int k = n - 1; k > 0; k--) {
for (int j = k - 1; j >= 0; j--) {
if (perm[j] <= perm[k]) {
perm[k]++;
}
}
}
// Print permutation
for (int k = 0; k < n; k++) {
printf("%d ", perm[k]);
}
printf("\n");
free(fact);
free(perm);
}调用 ithPermutation(10, 3628799) 返回十个元素的最后一个排列：
9 8 7 6 5 4 3 2 1 0
以上是我们怎样才能在不使用蛮力的情况下有效地找到第n个排列？的详细内容。更多信息请关注PHP中文网其他相关文章！
