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

发布于 2024-11-05 08:23:43 字数 538 浏览 1 评论 0原文

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

这是一道面试题。假设有一个按字典顺序排列的排列列表。例如，123、132、213、231、312、>321。给定一个排列，在这样的列表中找到它的索引。例如，排列213的索引是2（如果我们从0开始）。

简单地说，我们可以使用 next_permutation 算法按字典顺序生成下一个排列，但这会导致 O(N!) 解决方案，这显然是不可行的。还有更好的解决办法吗？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

爱的故事 2024-11-12 08:23:43

我想到了这个解决方案（但我还没有测试过）。

第一个数字的范围是 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)。

This solution came into my mind (but I didn't test it yet).

The first digit is from range 1 to N, thus you can derive from the first digit whether your permutation is in which block of size (N-1)!

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

Then you can recursively apply this to the next digits (which is one of (N-1)! permutations).

So with an arbitrary N you can do the following algorithm:

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

In your case:

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

Thus this algorithm is O(N^2).

回复收藏 0 原文

清醇 2024-11-12 08:23:43

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

例如，2 的索引为 1，而 13 的索引为 0，因此结果为 1 * (3-1)！ + 0 = 1 * 2 = 2。

回复收藏 0 原文

梦回旧景 2024-11-12 08:23:43

排列中的第一个元素为您提供 N! 的子范围
删除第一个元素
对剩余元素重新编号以删除间隙
递归

回复收藏 0 原文

勿忘初心 2024-11-12 08:23:43

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

In C using recursion it will be something like this

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

回复收藏 0 原文

~没有更多了~