查找排列的列表中给出的置换的指数字典顺序

Question

可能重复：
Given a string and permutation of the string. Find the index of this permuted string in the sorted list of the permutations of the string.

这是一个面试问题。让我们有一个按字典顺序排列的列表。例如，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）。

Answer 2

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

例如，2具有索引1，和13索引为0，所以结果是1 * (3-1)! + 0 = 1 * 2 = 2。

Answer 3

• 中排列第一个元素给你的N!
• 子范围删除第一个元素
• 重新编号剩余的元素去除空白
• 递归

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); 
}