# Write a program to print all permutations of a given string without repetition. (Repetition of characters is not allowed).

### Given a string of length n, print all permutation of the given string without Repetition . (Repetition of characters is NOT allowed)

Case 1
Input:   A
output: A

Case 2
Input: AB
output:
AB
BA

Case 3
Input:  ABC
output:
ABC
ACB
BAC
BCA
CAB
CBA

### Algorithm:

How many permutations is possible?

Lets see how many permutation is possible for given n character String.
In string "AB", n is 2
In string "ABC", n is 3
From above permutations displayed, we can see relation as n!.
So for "AB", total permutations are 2! = 2.
For "ABC", total permutations are 3! = 6.

How to print all permutation?

It is very easy, Lets take an example of String "ABC"

We will take recursive approach. In this approach important thing is base case.
We will try to make each permutation by adding characters one by one to the temporary
string  "permutation" that need to be printed and removing the same character one by one
from original string. As we are removing one by one character from original string and adding it to "permutation" string,   So it is sure at one point length of original String will be 0 and length of
"permutation" string will be 3.

So base case is, when the length of our original string became 0, we will print the string  "permutation" and return.

Now, how we will form "permutation" string is,
remove first character of original string and add it to "permutation" string and check the
length of original string which is not 0, true, so call function again,
"string" = "BC" "permutation" = "A"

remove first character of original string and add it to "permutation" string and check the
length of original string which is not 0, true, so call function again,
"string" = "C" "permutation" = "AB"

remove remaining character of original string and add it to "permutation" string and check the
length of original string which is not 0, false, so it is time to print the string "permutation".
"string" = "" "permutation" = "ABC"

1st permutation is ABC
after returning from printing 1st permutation,
"string" = "C" "permutation" = "AB"
Original string has only one character "C" whose permutation is covered,
no more permutation possible of one character string, so return,
"string" = "BC" "permutation" = "A"
From original string "ABC", we covered permutation keeping
"A", "B" at place and changing "C", which gave "ABC" as 1st permutation.
Now, its time to work on 2nd character of original string

Now,
remove second character of original string and add it to "permutation" string and check the
length of original string which is not 0, true, so call function again,
"string" = "B" "permutation" = "AC"

remove remaining character of original string and add it to "permutation" string and check the
length of original string which is not 0, false, so it is time to print the string "permutation".
"string" = "" "permutation" = "ACB"

if we continue the same process in a loop, then we will get all our permutations
without repetition of characters.

### Program to print all permutations of a string in Java

```package backtracking;

public class StringPermutationWithoutRepetition {

public static void main(String[] args) {
permutation("ABC");
}

private static void permutation(String string) {
printPermutation(string,"");
}

private static void printPermutation(String string, String permutation) {

if(string.length()==0){
System.out.println(permutation);
return;
}

for (int i = 0; i < string.length(); i++) {
char toAppendToPermutation = string.charAt(i);
String remaining = string.substring(0, i) + string.substring(i + 1);

printPermutation( remaining,  permutation + toAppendToPermutation);
}
}

}
```

### Time Complexity:

Time complexity of program to print all permutations of a string is O(n*n!).

How it comes to (n * n!)

From the above stack trace picture of a program you can see, for printing permutation of string "ABC" i.e. 3 character word, what it does is

Outer:
Keeping A at place, it finds all the permutations of remaining string, then,
Inner:
Keeping B at place, it finds all the permutations of remaining string, then,
keeping C at place, it finds all the permutations of remaining string, then,
Change B to C and find all the permutations of remaining string, then,
...........
...............
Keeping B at place, it finds all the permutations of remaining string, then,
...........
...........
Keeping C at place, it finds all the permutations of remaining string.

How many times Outer: label has to print is number of characters present in word.
that is n
How many times Inner: label has to print is number of permutations of a character present in word.
this brings n!

Now, if we read this line again,
Keeping Outer character at place, find all permutation of Inner sting, then replace
Outer character at place, and again find all permutation of Inner sting, and
so on till end of Outer character.

hence the complexity is O(n * n! )

Another nice way of printing permutations.
```package com.javabypatel;

import java.util.ArrayList;
import java.util.List;

public class StringPermutationWithoutRepetition {

public static void main(String[] args) {

List<Object> list = new ArrayList<Object>();
list.add("a");
list.add("b");
list.add("c");

int[] countList = new int[] {1, 1, 1};
Object[] result = new Object[list.size()];

printPermutations(list, countList, result, 0);
}

private static void printPermutations(List<Object> list, int[] countList, Object[] result, int pointer) {
if (pointer == list.size()) {
printArray(result);
return;
}

for (int i = 0; i < list.size(); i++) {
if (countList[i] == 0) {
continue;
}

result[pointer] = list.get(i);
countList[i] = countList[i] - 1;

printPermutations(list, countList, result, pointer + 1);

countList[i] = countList[i] + 1;
}
}

private static void printArray(Object input[]) {
for (Object ch : input) {
System.out.print(ch);
}
System.out.println();
}
}

```
Explanation: https://www.youtube.com/watch?v=nYFd7VHKyWQ

### You may also like to see

#### Print all subsets of a given set.

Enjoy !!!!

If you find any issue in post or face any error while implementing, Please comment.

#### 2 comments

Thanks for great explanation and great coding. What is the time complexity of your approach?

Reply

Thanks Hengame. I have updated the post and covered Time complexity. Please let me know if you find any difficulty in understanding it.

Reply