# Program to Find all the Permutations of a String

Program to Find all the Permutations of a String on fibonacci, factorial, prime, armstrong, swap, reverse, search, sort, stack, queue, array, linkedlist, tree, graph etc.

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

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

## 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("%s\n",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