Program to Find all the Permutations of a String

Q. Program to find all the permutations of a string.

To solve this problem, we need to understand the concept of backtracking.

According to the backtracking algorithm:

Fix a character in the first position and swap the rest of the character with the first character. Like in ABC, in the first iteration three strings are formed: ABC, BAC, and CBA by swapping A with A, B and C respectively.
Repeat step 1 for the rest of the characters like fixing second character B and so on.
Now swap again to go back to the previous position. E.g., from ABC, we formed ABC by fixing B again, and we backtrack to the previous position and swap B with C. So, now we got ABC and ACB.
Repeat these steps for BAC and CBA, to get all the permutations.

Algorithm

Define a string.
Fix a character and swap the rest of the characters.
Call the generatePermutation() for rest of the characters.
Backtrack and swap the characters again.

Solution

Python

 #Function for generating different permutations of the string def generatePermutation(string,start,end):     current = 0;     #Prints the permutations     if(start == end-1):         print(string);     else:          for current in range(start,end):         #Swapping the string by fixing a character             x = list(string);             temp = x[start];             x[start] = x[current];             x[current] = temp;        #Recursively calling function generatePermutation() for rest of the characters              generatePermutation(“”.join(x),start+1,end);             #Swapping the string by fixing a character             temp = x[start];             x[start] = x[current];             x[current] = temp;  str = “ABC” n = len(str); print(“All the permutations of the string are: “); generatePermutation(str,0,n); 

Output:

All the permutations of the string are:  ABC ACB BAC BCA CBA CAB

C

 #include<stdio.h> #include<string.h> //Declaring generatePermutation() void generatePermutation(char * , int , int );  int main() {   char str[] = “ABC”;   int n =strlen(str);   printf(“All the permutations of the string are: n”);   generatePermutation(str,0,n); }  //Function for generating different permutation of the string. void generatePermutation(char *str,const int start, int end) {   char temp;   int i,j;   for(i = start; i < end-1; ++i){   for(j = i+1; j < end; ++j)   {    //Swapping the string by fixing a character     temp = str[i];   str[i] = str[j];     str[j] = temp;     //Recursively calling function generatePermutation() for rest of the characters   generatePermutation(str , i+1 ,end);     //Backtracking and swapping the characters again     temp = str[i];     str[i] = str[j];     str[j] = temp;   }   }   //Print the permutations   printf(“%sn”,str); } 

Output:

All the permutations of the string are:  ABC ACB BAC BCA CBA CAB

JAVA

 public class PermuteString {     //Function for swapping the characters at position I with character at position j     public static String swapString(String a, int i, int j) {         char[] b =a.toCharArray();         char ch;         ch = b[i];         b[i] = b[j];         b[j] = ch;         return String.valueOf(b);     }          public static void main(String[] args)     {         String str = “ABC”;         int len = str.length();         System.out.println(“All the permutations of the string are: “);         generatePermutation(str, 0, len);     }          //Function for generating different permutations of the string     public static void generatePermutation(String str, int start, int end)     {         //Prints the permutations         if (start == end-1)             System.out.println(str);         else         {             for (int i = start; i < end; i++)             {                 //Swapping the string by fixing a character                 str = swapString(str,start,i);                 //Recursively calling function generatePermutation() for rest of the characters                  generatePermutation(str,start+1,end);                 //Backtracking and swapping the characters again.                 str = swapString(str,start,i);             }         }     } } 

Output:

All the permutations of the string are:  ABC ACB BAC BCA CBA CAB

C#

 using System;                     public class Program {     //Function for swapping the characters at position I with character at position j     public static String swapString(String a, int i, int j) {         char[] b =a.ToCharArray();         char ch;         ch = b[i];         b[i] = b[j];         b[j] = ch;         //Converting characters from array into single string         return string.Join(“”,b);     }          public static void Main()     {         String str = “ABC”;         int len = str.Length;         Console.WriteLine(“All the permutations of the string are: “);         generatePermutation(str, 0, len);              }      //Function for generating different permutations of the string     public static void generatePermutation(String str, int start, int end)     {         //Prints the permutations         if (start == end-1)             Console.WriteLine(str);         else         {             for (int i = start; i < end; i++)             {                 //Swapping the string by fixing a character                 str = swapString(str,start,i);                 //Recursively calling function generatePermutation() for rest of the characters                  generatePermutation(str,start+1,end);                 //Backtracking and swapping the characters again.                 str = swapString(str,start,i);             }         }     } } 

Output:

All the permutations of the string are:  ABC ACB BAC BCA CBA CAB

PHP

 <!DOCTYPE html>  <html>  <body>  <?php     //Function for generating different permutations of the string function generatePermutation($string,$start,$end){   if($start == $end-1){     echo “$string <br>”;   }   else{     for($i = $start; $i < $end; $i++){       //Swapping the string by fixing a character       $temp = $string[$start];       $string[$start] = $string[$i];       $string[$i] = $temp;      //Recursively calling function generatePermutation() for rest of the characters       generatePermutation($string,$start+1,$end);       //Backtracking and swapping the characters again.       $temp = $string[$start];       $string[$start] = $string[$i];       $string[$i] = $temp;     }   } } $str = “ABC”; $n = strlen($str); echo “All the permutations of the string are: <br>”; generatePermutation($str,0,$n); ?>  </body>  </html>  

Output:

All the permutations of the string are:  ABC ACB BAC BCA CBA CAB

Next TopicPrograms List

Q. Program to find all the permutations of a string.

Algorithm

Solution

Python

C

JAVA

C#

PHP

Potential Energy

Program to Find The Transpose of a Given Matrix

You may also like