**Problem**

Write a method to compute all permutations of a string.

**Example**

For a string of length n, there are n! permutations.

INPUT: "abc"

OUTPUT: "abc" "acb" "bac" "bca" "cab" "cba"

So, we have 3! = 6 items for string abc.

Solution

There are several ways to do this. Common methods use recursion, memoization, or dynamic programming.

The basic idea is that you produce a list of all strings of length 1, then in each iteration, for all strings produced in the last iteration, add that string concatenated with each character in the string individually. (the variable index in the code below keeps track of the start of the last and the next iteration)

Lets split up the problem in 2 cases - when duplicates are not allowed and when allowed.

Case 1 : If String has "NO" duplicate

**Method 1 - Recursion**

**Answer**: Here is a recursive solution to print all the permutations of a string.

The idea is to keep the first character constant and generate permutations with the rest. Then keep the first two characters constant and generate permutations with the rest until you are out of characters.

So for string "abc", the idea is that the permutations of string abc are a + permutations of string bc, b + permutations of string ac and so on.

The following piece of a code is a very efficient use of recursion to find the possible permutation of a string.

**Caution**: However, this solution does not take care of duplicates. It is assumed that there are no duplicates in the string.

public class Permutations { public static void permutate(String s) { permutateHelper("", s); } //Helper function private static void permutateHelper(String prefix, String rest) { int N = rest.length(); if (N == 0) System.out.println(prefix); else { for(int i = 0; i < N; i++){ perm1(prefix + rest.charAt(i), rest.substring(0, i) + rest.substring(i+1, N)); } } } public static void main(String[] args) { String alphabet = "Testt"; String elements = alphabet.substring(0, alphabet.length()); perm1(elements); } }

__Dry running the code__

`---ABC`

A---BC

AB---C

ABC---

-------------------------------ABC

AC---B

ACB---

-------------------------------ACB

B---AC

BA---C

BAC---

-------------------------------BAC

BC---A

BCA---

-------------------------------BCA

C---AB

CA---B

CAB---

-------------------------------CAB

CB---A

CBA---

-------------------------------CBA

**Method 1b) Recursion and Backtracking**

This will also not work for duplicates. I left out the implementation of the swap method since that implementation is not important here.

//actual helper function void permutateHelper( char[] str, int index ) { int i = 0; if( index == strlen(str) ) { // We have a permutation so print it printf(str); return; } for( i = index; i < strlen(str); i++ ) { swap( str[index], str[i] ); // It doesn't matter how you swap. permutateHelper( str, index + 1 ); swap( str[index], str[i] ); } } //actual function public static void permutate( char[] str ){ permutateHelper (str, 0); } //calling the function permutate("abcdefgh".toCharArray());

Case 2 : If String has duplicate

What do we do if there are duplicates in the string?

**Solution 1:**

The trick is to sort the characters in the alphabetical order first. We can then ignore the duplicates easily when generate the permutation.

**Solution 2**

void permutateHelperDuplicate(String prefix, String rest){ int N = 0; if(rest!=null) N = rest.length(); if (N==0) { System.out.println(prefix); } else { for (int i = 0; i < rest.length(); i++) { //test if rest[i] is unique. boolean found = false; for (int j = 0; j < i; j++) { if (rest.charAt(j) == rest.charAt(i)) //rest[j]==rest[i] found = true; } if(found) continue; String newPrefix = prefix + rest.charAt(i); String newRest = rest.substring(0, i) + rest.substring(i+1,N); permutateHelperDuplicate(newPrefix, newRest); } } }

**Method 3 - Use HashSet**

In this method, we can have an hashset of string, and once we generate the permutation, we add it to hashset if it is not there, otherwise we ignore it.

Please let me know if you any suggestions.

small trick ,but a very nice solution for duplicates!!!!

ReplyDeleteThanks Nikhil. :)

ReplyDeletecan u please write the main function for duplicate program. I ran the duplicate program and it is not giving me the desired output

ReplyDelete