Print all the permutations of a string in C

Question

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!

How is the backtracking applied?

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

Solution 1

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.

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

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

Solution 2

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)).

Backtracking is applied by calling swap() twice effective undoing its original 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));

Solution 3

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).

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

Solution 4

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

Solution 5

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]='\0';
        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;
}

View more solutions

Comments

[Oliver Charlesworth]

Why don't you add some helpful printfs, and then try running it?

[Rahil Wazir]

There is extra curl brace remove it.

[CuriousBenjamin]

geeksforgeeks.org/…

[Deepankar Singh]

Can you give some test where OP's algo fails and your algo gives right result. I am calling OP's algo by passing starting and ending index of the string and it's giving right result every time.

[chux - Reinstate Monica]

@Deepankar Singh 1) Clarify "ending index of the string", Does s[ending_ index] == '\0' or is s[ending_ index+1] == '\0'? Does your tests include odd/even length strings and 0 length strings?

[chux - Reinstate Monica]

@Deepankar Singh The key issue with OP's post is not clearly posting how n is determined for the initial call - which likely is a result of inadequate documentation on the sites researched. Using int n = strlen("abc"); permute("abc",0,n) looks reasonable. "abc"[3] is the null character, which is the last character of the string, so could be considered the "ending index of the string". Yet I think for OP code to work, int n = strlen("abc") - 1; is needed. Unfortunately that has niche issues with permute("",0,strlen("")-1) and n as strlen(s)-1 is counterintuitive.

[chux - Reinstate Monica]

Agree with @Ashish, this is a nice solution for C++. This post is tagged C and the above code does not obviously convert. Perhaps posting a C solution?

[Deepankar Singh]

I agree OP didn't specify the initial value of n, but seeing his for loop condition "j <= n" , it can be inferred that initial value of n is nothing but strlen("abc")-1 which gives correct result for every test cases. Anyway I got your point why you assumed OP's algo can have 2 problems. :)

[chux - Reinstate Monica]

@Deepankar Singh Many times a function declaration in a .h file is the primary documentation. Consider a lone void permute(char *a, int i, int n), what would one expect? With OP: "I am not able to understand the recursion method" - some problem exist. I first thought n was array size, and then string length, but no - it is string length minus 1. Code could have been void permute(char *a, int i, int length_minus_1)

[j b]

@chux this isn't C++, I think it's Java