C语言 在 C 中打印字符串的所有排列

Print all the permutations of a string in C

提问by poorvank

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 algorithmfor permutation but I am not able to understand the recursion method. I searched the web and found this code:

我正在学习回溯和递归，并且坚持使用打印字符串所有排列的算法。我使用bell算法进行排列解决了它，但我无法理解递归方法。我在网上搜索并找到了这段代码：

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!

这个算法基本上是如何工作的，我无法理解？我什至尝试过干跑！

How is the backtracking applied?

回溯是如何应用的？

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

并且在计算置换方面是否比贝尔算法更有效？

回答by bengoesboom

The algorithm basically works on this logic:

该算法基本上适用于以下逻辑：

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.

字符串 X 的所有排列与 X 中每个可能字符的所有排列相同，再加上字符串 X 中不含该字母的所有排列。

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

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

• "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"

• “a”与“bcd”的所有排列连接
• “b”与“acd”的所有排列连接
• “c”与“bad”的所有排列连接
• “d”与“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.

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

回答by chux - Reinstate Monica

The code has 2 problems, both related to n, the assumed length of the string. The code for (j = i; j <= n; j++) { swap((a+i), (a+j)); ...swap in string's null character '\0'and gives code truncated results. Check the original (i == n)which should be (i == (n-1)).

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

Backtracking is applied by calling swap()twice effective undoing its original swap.

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

The order of complexity is the same for Bell Algorithm.

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

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

回答by Shubham Mittal

The code that you found is correct! The algorithm swaps the current character in the string with all the subsequent characters and recursively calling the function. Its difficult to explain in words. The figure below may be of some help to you.

您找到的代码是正确的！该算法将字符串中的当前字符与所有后续字符交换并递归调用该函数。很难用语言来解释。下图或许对你有帮助。

Backracking is being done in the 2nd swap for reversing the effect of the 1st swap i.e. we are going back to the original string and will now swap the next character in the array with the current character. The time complexity of the algo. is O(n*n!) since the loop runs n times and the permute function is called n! times. (For the 1st iteration, its called n times; for 2nd iteration (n-1) times and so on).

在第二次交换中进行回退，以逆转第一次交换的效果，即我们将返回原始字符串，现在将数组中的下一个字符与当前字符交换。算法的时间复杂度。是 O(n*n!) 因为循环运行了 n 次并且置换函数被称为 n! 次。（对于第一次迭代，称为 n 次；对于第二次迭代 (n-1) 次，依此类推）。

Source: http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

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

回答by Nikhil_10

Recursion really simplifies it:

递归确实简化了它：

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

回答by Nmzzz

Pseudo code:

伪代码：

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

回答by Manish Bhadani

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<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
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<len-1;i++)
    {
        array[50]='
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
';
        dead=0;
        for(int j=cnum;j<len+cnum;j++)
        {
            mid=j%len;
            if(mid==cnum && flag==1)
            {
                cout<<str[mid];
                array[dead]=mid;
                dead++;
                flag=0;
            }
                else
            {
                giga=(i+j)%len;
                for(int k=0;k<dead;k++)                 
                {
                    if((array[k]==giga) && flag==0)
                    {
                    giga=(giga+1)%len;
                    }
                }
                cout<<str[giga];
                array[dead]=giga;
                dead++;

            }
        }
        cout<<endl;
        flag=1; 
    }
}
int main()
{
    cout<<"Enter the string :: ";
    getline(cin,str);
    len=str.length();
    cout<<"String length = "<<len<<endl;
    cout<<"Total permutation = "<<len*(len-1)<<endl;
    for(int j=0;j<len;j++)
    {
        permutation(j);
    }
return 0;
}

回答by Frank Denis

# include <stdio.h>

/* 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;
}

回答by user3424474

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 i.e. 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 i.e. 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 i.e. 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 i.e. 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 i.e. 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 i.e. 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 i.e. 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 i.e. 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 i.e. 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--------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------

回答by AbhimanyuAryan

I faced the same problem analysing the execution of this backtrack algorithm at GeeksForGeeks. See for yourself how this executes. Sometimes printing values really help visualise the execution of program

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

##代码##