在按字典顺序排列的列表中找到给定排列的索引
问题内容：
这是一个面试问题。让我们按字典顺序列出排列顺序。例如123，132，213，231，312，321。给定排列，在这样的列表中找到其索引。例如，置换的索引213是2（如果我们从0开始）。
琐碎地，我们可以使用一种next_permutation算法来按字典顺序生成下一个排列，但这会导致O（N！）解，这显然是不可行的。有没有更好的解决方案？
问题答案：
我想到了这个解决方案（但我尚未对其进行测试）。
第一位数字的范围是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）。
