寻找给定字符串的所有可能排列

Question

我这里只是想解决一个看起来很有趣的问题。我试着去思考它，但却找不到有效的解决方法。也许我的概念还在建立中... 不管怎样，问题如下：

想要找出给定字符串的所有可能排列...... 同时，如果有任何可能的变化，请分享。

我在网络上找到了一种使用递归的解决方案.. 但这似乎有些错误，不太令人满意。

程序如下：

void permute(char s[], int d)
{
   int i;

   if(d == strlen(s))
      printf("%s",s);

   else
   {
      for(i=d;i<strlen(s);i++)
      {
         swap(s[d],s[i]);
         permute(s,d+1);
         swap(s[d],s[i]);
      }
   }
}

如果这个程序看起来没问题（当我运行它时出现错误），请提供一个小例子来理解它，因为我还在学习递归的概念。

如果有任何其他有效的算法存在，也可以讨论...

请注意，这不是作业...

谢谢...

- AGeek

---

按照定义，这不是n！的时间复杂度吗？ - Tyler

不，这不是 n!：(1) 对于递归中每个叶子的 printf，它是 n×n!，(2) 对于每个递归级别上重复的 strlen，大约是 n²×n!。通过更加小心地编程，您可以轻松摆脱 (2) 中的额外 n 因素。 - Jens Gustedt

Answer 1

代码看起来正确，但你只有算法的核心部分，还没有完整的程序。你需要提供缺失的部分：头文件、一个主函数和一个swap宏（你可以通过调用`swap(s, d, i)`使`swap`成为一个函数）。

为了理解这个算法，最好添加一些跟踪输出，比如在`permute`函数的开头添加`printf("permute(%s, %d)", s, d)`，然后使用一个3或4个字符的字符串运行程序。

基本原理是每次递归调用`permute`都将剩余的每个元素依次放在位置`d`上；之前处于位置`d`的元素被保存，因为它被放置在之前提到的剩余元素所在的位置上（即元素被交换）。对于每个放置，`permute`被递归调用以生成在位置`d`之后的所有期望子字符串。因此，顶层调用（d=0）一次尝试位置0中的所有元素，第二级调用（d=1）尝试除已经在位置0中的元素之外的所有元素等等。次底层调用（d=n-1）有一个要尝试放在最后一个位置上的单个元素，而最深层调用（d=n）则打印出生成的排列。

核心算法需要Θ(n·n!)的运行时间，这是最好的可能性，因为这是输出的大小。但是，该实现不够高效，因为它在每次迭代时都会重新计算`strlen(s)`，导致Θ(n²·n!)的运行时间；简单的修复方法是预先计算长度，从而得到Θ(n·n!)。该实现需要Θ(n)的内存，这是可能的最佳情况，因为这是输入的大小。

- Gilles 'SO- stop being evil'

---

您的复杂度观察并不完全正确。由于每个递归级别上都有愚蠢的 strlen，因此在给出实现形式的情况下，它是 Θ(n²×n!)。 - Jens Gustedt

Answer 2

关于递归的解释，请参考Gilles的答案。

您的代码存在一些问题。首先，在C语言中实现所需的swap函数将会很困难，因为C语言缺乏按引用调用的概念。您可以尝试使用宏来实现这个功能，但是那样的话，您要么必须使用异或技巧来原地交换值，要么使用临时变量。

然后，您在每个递归级别上重复使用strlen会使程序的复杂度爆炸。就像您所给出的那样，在每个递归级别的每次迭代中都会执行此操作。由于您的字符串甚至会因为swap而发生改变，编译器甚至无法注意到这总是相同的。因此，他将无法优化任何内容。如果您像这样实现它，搜索字符串中的终止符'\0'将远远超过所有其他指令。

- Jens Gustedt