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?

Answer 1

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/

Answer 2

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 3

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

Answer 4

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

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

Answer 6

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

Answer 7

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

Answer 8

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.