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

Question

可能重复:
给定字符串和字符串的排列.在字符串排列的排序列表中查找此置换字符串的索引.

这是一个面试问题.让按字典顺序列出排列.例如123,132,213,231,312,321.给定排列在这样的列表中找到它的索引.例如,置换索引213是2(如果我们从0开始).

平凡地说,我们可以使用next_permutation算法以字典顺序生成下一个排列,但它导致O(N!)解,这显然是不可行的.有没有更好的解决方案？

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)。