c - 在 C 中打印字符串的所有排列

Question

我正在学习回溯和递归，我被困在一个打印字符串所有排列的算法上。我使用 bell algorithm 解决了它用于排列，但我无法理解递归方法。我在网上搜索并找到了这段代码:

void permute(char *a, int i, int n) 
{
   int j; 
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); 
       }
   }
} 

我无法理解这个算法的基本原理是什么？我什至试过试运行!

如何应用回溯？

在排列计算上是否比贝尔算法更高效？

Answer 1

该算法基本上按照以下逻辑工作:

字符串 X 的所有排列等同于 X 中每个可能字符的所有排列，以及字符串 X 中没有该字母的所有排列。

也就是说，“abcd”的所有排列都是

• “a”与“bcd”的所有排列连接
• “b”与“acd”的所有排列连接
• “c”与“bad”的所有排列组合
• “d”与“bca”的所有排列组合

特别是该算法不是对子字符串执行递归，而是对输入字符串执行递归，不使用额外的内存来分配子字符串。 “回溯”撤消对字符串的更改，使其保持原始状态。