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

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

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)); ... for (j = i; j <= n; j++) { swap((a+i), (a+j)); ...交换字符串的空字符'\0'并给出代码截断结果。 检查原始(i == n)应该是(i == (n-1)) 。

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

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

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

Answer 5

伪代码：

 String permute(String a[]) { if (a[].length == 1) return a[]; for (i = 0, i < a[].length(); i++) append(a[i], permute(a[].remove(i))); } 

Answer 6

 I create more specific but not efficient Program for permutation for general string. It's work nice way. //ubuntu 13.10 and g++ compiler but it's works on any platform and OS //All Permutation of general string. #include #include #include #include using namespace std; int len; string str; void permutation(int cnum) { int mid; int flag=1; int giga=0; int dead=0; int array[50]; for(int i=0;i
		      	
 # include  /* Function to swap values at two pointers */ void swap (char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } /* Function to print permutations of string This function takes three parameters: 1. String 2. Starting index of the string 3. Ending index of the string. */ 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)); //backtrack } } } /* Driver program to test above functions */ int main() { char a[] = "ABC"; permute(a, 0, 2); getchar(); return 0; } 

Answer 7

 def perms(s): if len(s) < 1: return [s] ps = [] for i in range(0, len(s)): head, tail = s[i], s[0:i] + s[i + 1:] ps.extend([head + tailp for tailp in perms(tail)]) return ps 

Answer 8

我在GeeksForGeeks分析了这个回溯算法的执行时遇到了同样的问题。 亲自看看这是如何执行的。 有时，打印值确实有助于可视化程序的执行

 swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 0 //////// l = 0 //////// r = 2 //////// string = ABC permute(a, l+1, r); ==== Values send to permute ie string= ABC //////// (l+1) = 1 //////// r = 2 swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 1 //////// l = 1 //////// r = 2 //////// string = ABC permute(a, l+1, r); ==== Values send to permute ie string= ABC //////// (l+1) = 2 //////// r = 2 ABC ______________________________________________________________________ swap((a+l), (a+i));++++ Backtract swap //////// i= 1 //////// l = 1 //////// r = 2 //////// string = ABC --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- ------------------------------END OF BACKTRACK-------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 2 //////// l = 1 //////// r = 2 //////// string = ACB permute(a, l+1, r); ==== Values send to permute ie string= ACB //////// (l+1) = 2 //////// r = 2 ACB ______________________________________________________________________ swap((a+l), (a+i));++++ Backtract swap //////// i= 2 //////// l = 1 //////// r = 2 //////// string = ABC --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- ------------------------------END OF BACKTRACK-------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- swap((a+l), (a+i));++++ Backtract swap //////// i= 0 //////// l = 0 //////// r = 2 //////// string = ABC --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- ------------------------------END OF BACKTRACK-------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 1 //////// l = 0 //////// r = 2 //////// string = BAC permute(a, l+1, r); ==== Values send to permute ie string= BAC //////// (l+1) = 1 //////// r = 2 swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 1 //////// l = 1 //////// r = 2 //////// string = BAC permute(a, l+1, r); ==== Values send to permute ie string= BAC //////// (l+1) = 2 //////// r = 2 BAC ______________________________________________________________________ swap((a+l), (a+i));++++ Backtract swap //////// i= 1 //////// l = 1 //////// r = 2 //////// string = BAC --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- ------------------------------END OF BACKTRACK-------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 2 //////// l = 1 //////// r = 2 //////// string = BCA permute(a, l+1, r); ==== Values send to permute ie string= BCA //////// (l+1) = 2 //////// r = 2 BCA ______________________________________________________________________ swap((a+l), (a+i));++++ Backtract swap //////// i= 2 //////// l = 1 //////// r = 2 //////// string = BAC --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- ------------------------------END OF BACKTRACK-------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- swap((a+l), (a+i));++++ Backtract swap //////// i= 1 //////// l = 0 //////// r = 2 //////// string = ABC --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- ------------------------------END OF BACKTRACK-------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 2 //////// l = 0 //////// r = 2 //////// string = CBA permute(a, l+1, r); ==== Values send to permute ie string= CBA //////// (l+1) = 1 //////// r = 2 swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 1 //////// l = 1 //////// r = 2 //////// string = CBA permute(a, l+1, r); ==== Values send to permute ie string= CBA //////// (l+1) = 2 //////// r = 2 CBA ______________________________________________________________________ swap((a+l), (a+i));++++ Backtract swap //////// i= 1 //////// l = 1 //////// r = 2 //////// string = CBA --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- ------------------------------END OF BACKTRACK-------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 2 //////// l = 1 //////// r = 2 //////// string = CAB permute(a, l+1, r); ==== Values send to permute ie string= CAB //////// (l+1) = 2 //////// r = 2 CAB ______________________________________________________________________ swap((a+l), (a+i));++++ Backtract swap //////// i= 2 //////// l = 1 //////// r = 2 //////// string = CBA --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- ------------------------------END OF BACKTRACK-------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- swap((a+l), (a+i));++++ Backtract swap //////// i= 2 //////// l = 0 //////// r = 2 //////// string = ABC --------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- ------------------------------END OF BACKTRACK-------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------