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

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

#### Print all combinations/permutations of a string of length k that can be formed from a set of n characters.

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

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

Reply## Post a Comment