打印字符串在C中的所有排列 [英] Print all the permutations of a string in C

问题描述

我学习的回溯和递归，我停留在一个算法用于打印字符串的所有排列。我解决了它使用的是钟算法的置换​​，但我不能够理解的递归方法。我在网上搜索，发现这个code：

I am learning backtracking and recursion and I am stuck at an algorithm for printing all the permutations of a string. I solved it using the bell algorithm for permutation but I am not able to understand the recursion method. I searched the web and found this code:

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

这是怎么算法基本工作，我无法理解？我甚至尝试空转！

How is this algorithm basically working I am unable to understand? I even tried dry running!

回溯是怎样应用？

和它比贝尔算法更有效的置换计​​算？

And is it more efficient than the Bell Algorithm for calculation of permutation?

推荐答案

算法大致在这样的逻辑：

The algorithm basically works on this logic:

字符串X的所有排列是同样的事情，在X各自可能的字符的所有排列，加上字符串X的所有排列，而不在它那封信。

All permutations of a string X is the same thing as all permutations of each possible character in X, combined with all permutations of the string X without that letter in it.

也就是说，的ABCD的所有排列是

That is to say, all permutations of "abcd" are

• 在一个联接与BCD
的所有排列
• 在B连接在一起ACD
的所有排列
• 在C连接在一起坏
的所有排列
• 在D串联起来的BCA
所有排列

• "a" concatenated with all permutations of "bcd"
• "b" concatenated with all permutations of "acd"
• "c" concatenated with all permutations of "bad"
• "d" concatenated with all permutations of "bca"

这个算法特别，而不是在子进行递归，采用了无需额外的内存分配子执行到位输入字符串的递归。而回溯撤消更改到字符串，使其处于原始状态。

This algorithm in particular instead of performing recursion on substrings, performs the recursion in place on the input string, using up no additional memory for allocating substrings. The "backtracking" undoes the changes to the string, leaving it in its original state.

这篇关于打印字符串在C中的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！