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

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

我想到了这个解决方案（但我尚未对其进行测试）。

第一位数字的范围是1到N，因此您可以从第一位数字得出排列是否在（N-1）个块中！

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

然后，您可以将其递归地应用于下一个数字（这是（N-1）！排列之一）。

因此，使用任意N可以执行以下算法：

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

在您的情况下：

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

因此，该算法为O（N ^ 2）。