在按字典顺序排列的排列列表中查找给定排列的索引

Question

这是一个面试题。假设有一个按字典顺序排列的排列列表，例如123，132，213，231，312，321。给定一个排列，找到它在该列表中的索引。例如，排列213的索引为2（如果我们从0开始）。

显然，我们可以使用next_permutation算法生成按字典顺序排列的下一个排列，但这会导致O(N!)的解决方案，这显然是不可行的。是否有更好的解决方案？

- Michael

Answer 1

我有一个解决方案（但我还没有测试过）。

第一个数字来自1到N的范围，因此您可以从第一个数字推断出您的排列在大小为(N-1)!的哪个块中。

2*(2!) + X where X = 0..2!-1

接下来你可以递归地将这个方法应用到下一位数字上（这是(N-1)!种排列中的一种）。

所以对于任意给定的N，你可以使用以下算法：

X = 0
while string <> ""
  X += ((first digit) - 1) * (N-1)!
  decrease all digits in string by 1 which are > first digit
  remove first digit from string
  N -= 1
return X

在你的情况下：

X = 2
s = "213"
X += (2-1) * 2! => 2
s = "12"
X += (1-1) * 1! => 2
s = "1"
X += (1-1) * 0! => 2

因此，该算法的时间复杂度为O(N^2)。

- Howard

---

我能够理解你的大部分回答，除了第一个代码块：2*(2!) + X where X = 0..2!-1。请问您能否解释一下这段代码的作用呢？我不理解等号右边的内容。 - Bowen Liu

Answer 2

将排列中第一个数字的索引乘以(n-1)!，并加上剩余排列的索引。

例如，2 的索引为 1，13 的索引为 0，因此结果为 1 * (3-1)! + 0 = 1 * 2 = 2。

- starblue

Answer 3

• 排列中的第一个元素给出了N!个子范围
• 删除第一个元素
• 重新编号其余元素以消除间隙
• 递归

- Simon Nickerson

Answer 4

在C语言中使用递归，代码如下：

int index(char *abc, int size)  
{   
   if(abc ==0 || *abc==0 || size == 0)  
  {  
    return 0;;  
  }  
  return ((abc[0] - '0') * pow(2,size-1)) + index(abc + 1, size -1);   
}

- Manoj R