Permutation

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

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.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.