用C打印字符串的所有排列

Question

我正在学习回溯和递归,我坚持使用一种算法来打印字符串的所有排列.我用置换算法求解了它,但是我无法理解递归方法.我在网上搜索并找到了这段代码:

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"与所有"坏"的排列联系在一起
• "d"与"bca"的所有排列联系在一起

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

Answer 2

该代码具有2个问题,既涉及到n,该字符串的假定长度.代码for (j = i; j <= n; j++) { swap((a+i), (a+j)); ...交换字符串的空字符'\0'并给出代码截断结果.检查原件(i == n)应该是什么(i == (n-1)).

通过调用swap()两次有效撤消其原始交换来应用回溯.

贝尔算法的复杂度顺序是相同的.

#include <stdio.h>

void swap(char *a, char *b) { char t = *a; *a = *b; *b = t; }

void permute(char *a, int i, int n) {
   // If we are at the last letter, print it
   if (i == (n-1)) printf("%s\n", a);
   else {
     // Show all the permutations with the first i-1 letters fixed and 
     // swapping the i'th letter for each of the remaining ones.
     for (int j = i; j < n; j++) {
       swap((a+i), (a+j));
       permute(a, i+1, n);
       swap((a+i), (a+j));
     }
  }
}

char s[100];
strcpy(s, "ABCD");
permute(s, 0, strlen(s));

Answer 3

您找到的代码是正确的!该算法将字符串中的当前字符与所有后续字符交换,并递归调用该函数.用文字难以解释.下图可能会对您有所帮助.

Backracking正在第二次交换中完成,以反转第一次交换的效果,即我们将返回到原始字符串,现在将使用当前字符交换数组中的下一个字符.算法的时间复杂性.因为循环运行n次并且置换函数被称为n,所以是O(n*n!)!倍.(对于第一次迭代,它被称为n次;对于第二次迭代(n-1)次,依此类推).

资料来源:http://www.geeksforgeeks.org/write-ac-program-to-print-all-permutations-of-a-given-string/

Answer 4

递归真的简化了它:

public static void permutation(String str) 
{ 
    permutation("", str); 
}

private static void permutation(String prefix, String str) 
{
    int n = str.length();
    if (n == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}