给定字典索引的n-2个排列(有重复)的算法

Question

我正在尝试找到一种方法来确定n-2个数字的排列，允许重复)从一组n个数字中，给定其字典索引。我们这样做的一个原因是找到Prufer代码，给定一个索引。考虑到一组数字为1,2,3,4，我们将得到一组n-2排列为1,1，1,2，1,3，1，4……4，3，4。我的问题是，在给定索引作为输入的情况下，是否有一种方法可以获得这样的排列，而无需枚举所有排列。我查看了这个链接Finding the index of a given permutation中的方法，但这可能与n-2个对象的排列有关。谢谢你。

Answer 1

这不是编程问题，而是更多的理解问题。Prufer序列它是一系列或线性应用程序，用于标记一组数字的每个可能的排列，标记每个标识是唯一的；因此，您可以定义a0、a1、a2、...、an-1的Prufer序列，例如

S = [a0,a1, ..., an-1], S in N

S -Prufer-> S x S

0 --------> [a0, a0]
1 --------> [a0, a1]
      ...
n-1 ------> [a0, an-1]
n --------> [a1, a0]
n+1 ------> [a1, a1]
      ...
2n-1 -----> [a1, an-1]
2n -------> [a2, a0]
2n+1 -----> [a2, a1]

以此类推。然后，在一般情况下，您可以只确定索引为i的排列

P(i) = [a_sub_(i/n), a_sub(i modulus n)].

请注意，这个Prufer系列只是一个简单例子:您可以定义自己的，记住它必须始终标识整个排列集，并使每个标识唯一(即，基础代数中的一个双向线性应用程序)。

Answer 2

以下是M69想法的一些JavaScript代码：

​

function f(rank, arr){
  var n = arr.length,
      res = new Array(n - 2).fill(arr[0]),
      i = n - 3;
 
  while (rank){
    res[i--] = arr[rank % n];
    rank = Math.floor(rank / n); 
  }
  
  return res;
}

console.log(f(64, ['a','b','c','d','e']));

​