按字典顺序查找排列列表中给定排列的索引[重复]

可能的重复：
给定一个字符串和该字符串的排列。在字符串排列的排序列表中查找该排列字符串的索引。

这是一道面试题。假设有一个按字典顺序排列的排列列表。例如，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)。