c - 给定词典索引查找 n-2 排列(带重复)的算法

Question

我正在尝试找到一种方法，根据其词典索引，从一组 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 个对象的排列有问题。谢谢。

Answer 1

可以通过将秩转换为以 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;
    }
}

(以上代码假定有效输入)