In this post I would be discussing generation of all permutation of a string. Permutation means “any of the different ways in which a set of things can be ordered”, for example, the possible permutations of x, y and z are xyz, xzy, yxz, yzx, zxy and zyx. We would also suppress generation of identical string in case there is a reptition of characters in the original string. For example, “iit” would result in “iit”, “iti” and “tii” ; instead of “iit”, “iti”, “iit”, “iti”, “tii” and “tii”.
Permutation
Let us understand the concept with the help of an example. The permutation of the string “VINAY” is:
VINAY VINYA VIANY VIAYN VIYAN VIYNA VNIAY VNIYA VNAIY VNAYI VNYAI VNYIA VANIY VANYI VAINY VAIYN VAYIN VAYNI VYNAI VYNIA VYANI VYAIN VYIAN VYINA IVNAY IVNYA IVANY IVAYN IVYAN IVYNA INVAY INVYA INAVY INAYV INYAV INYVA IANVY IANYV IAVNY IAVYN IAYVN IAYNV IYNAV IYNVA IYANV IYAVN IYVAN IYVNA NIVAY NIVYA NIAVY NIAYV NIYAV NIYVA NVIAY NVIYA NVAIY NVAYI NVYAI NVYIA NAVIY NAVYI NAIVY NAIYV NAYIV NAYVI NYVAI NYVIA NYAVI NYAIV NYIAV NYIVA AINVY AINYV AIVNY AIVYN AIYVN AIYNV ANIVY ANIYV ANVIY ANVYI ANYVI ANYIV AVNIY AVNYI AVINY AVIYN AVYIN AVYNI AYNVI AYNIV AYVNI AYVIN AYIVN AYINV YINAV YINVA YIANV YIAVN YIVAN YIVNA YNIAV YNIVA YNAIV YNAVI YNVAI YNVIA YANIV YANVI YAINV YAIVN YAVIN YAVNI YVNAI YVNIA YVANI YVAIN YVIAN YVINA
Notice that position of ‘V’ is fixed and the remaining character are being permuted. Then position of the first character and second character is swapped and the remaining character are permuted. This repeated for first two character, then first three character and so on. Let us generalize this pattern for a string for string S. Generate and print all permutations of S, manupulating only those characters which occur between some position K and the end of the string. The Java program to generate permutation of all characters in a string is as follows:
class PermutateArray{
public static void printArray(char a[] ){
for( char ch: a ){
System.out.print(ch);
}
System.out.println();
}
public static void permute( char s[], int k ){
if(k==s.length-1){
printArray(s);
}else{
char temp;
for(int i = k; i < s.length; i++){
if( s[i] == s[k] && i!=k ) continue;
temp = s[k];
s[k]= s[i];
s[i] = temp;
permute(s, k+1);
temp = s[k];
s[k]= s[i];
s[i] = temp;
}
}
}
public static void permute( String str ){
char a[] = str.toCharArray();
permute(a,0);
}
public static void main(String args[]){
permute("iit") ;
}
}
In the above program the function permute() is overloaded. The public function permute() which accepts only one argument is the wrapper function which would be invoked to permute the string. This public permute would then invoke the private function permute() with two arguments, the string and the position k, which would invoke itself recursively until exit conditions is reached (that is k is equal to s.length – 1). Line number 14, is used to skip the permutation if the character being swapped are identical.
The above program can be made somewhat more elegant if we use the StringBuilder class as follows:
class Permutation{
public static void permute( StringBuilder s, int k ){
int length=s.length();
if(k==length-1){
System.out.println(s);
}else{
char temp;
for(int i = k; i < length; i++){
if( s.charAt(i) == s.charAt(k) && i!=k ) continue;
temp = s.charAt(k);
s.setCharAt(k, s.charAt(i) );
s.setCharAt(i, temp );
permute(s, k+1);
temp = s.charAt(k);
s.setCharAt(k, s.charAt(i) );
s.setCharAt(i, temp );
}
}
}
public static void permute( String str ){
str=str.toUpperCase();
permute(new StringBuilder(str.toUpperCase()),0);
}
public static void main(String args[]){
permute("it") ;
}
}
As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.