我正在尝试找到一种方法，根据其词典索引，从一组 n 个数字中确定 n-2 个数字的排列，允许重复)。我们这样做的一个原因是在给定索引的情况下找到 Prufer 代码。 将一组数字视为 [1,2,3,4]，我们将得到一组 n-2 排列，如 [1,1]、[1,2]、[1,3]、[1,4]。 .....[4,3]、[4,4]。 我的问题是，是否有一种方法可以在不枚举所有排列的情况下，将索引作为输入来获得这样的排列。我查看了此链接中的方法 Finding the index of a given permutation但这可能对 n-2 个对象的排列有问题。谢谢。
最佳答案
可以通过将秩转换为以 n 为底的数字并将其数字解释为从 0 开始的索引来计算一组 n 个数字中具有给定秩的排列:
set: [1,2,3,4]
0-based rank: 9
9 in base-4: 21
0-based indexes: [2,1]
permutation: [3,2]
set: [a,b,c,d,e]
0-based rank: 64
64 in base-5: 224
0-based indexes: [2,2,4]
permutation: [c,c,e]
像这样的东西应该可以解决问题，其中 set 是一个包含 n 个数字的 int 数组，而 perm 是一个足以容纳 n-2 的 int 数组数字:
void permutation(int *set, int n, int rank, int *perm) {
for (int k = n - 2; k > 0; --k) {
perm[k - 1] = set[rank % n];
rank /= n;
}
}
(以上代码假定有效输入)
关于c - 给定词典索引查找 n-2 排列(带重复)的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43007315/