Iterative Permutation of String : Java

Program Description :

The program computes all the unique permutations of a string of characters with no duplicate characters and white spaces. The permutations are printed in lexicographic form.

We use the iterative algorithm here whereas the recursive version can also be used for computation depending on the requirements of the user. 


Algorithm

The original string is taken as the input and duplicate characters and white spaces are removed from the string usng the user defined removeInvalid(String) function. Then the string is converted into an array of characters using the toCharArray() function and stored in the variable S[]. The characters are sorted in ascending order using the bubble sort technique. The next permutation can be generated by executing the following steps iteratively:
  • Scanning the array from the end such that i is the second-last element. run the loop till S[i] remains greater than S[i+1] i.e. S[i] > S[i+1].
  • Now, if the value of i is found to be less than 0 i.e. i < 0, we are able to conclude that no more permutations are possible.
  • Run the loop again from the end with a variable j until we get a position where S[j] > S[i].
  • Swapping the elements at S[i] and S[j].
  • Now we have the reverse the elements in the remaining array after i.
  • Thus, now we have the next permutation generated and the function returns true.
  • Use a while loop to iterate the sequence till the function returns false.
The loop which calls the function will iterate automatically factorial n times (n!) where n is the number of characters in the final array. All the permutations will be in lexicographic order. This program is faster and memory efficient when compared to the recursive variant.

Program Sample Output :



Iterative Permutations Sample Output


Java Program Source Code :

/**
 * The class PermutationIterative computes all the Unique Permutations
 * of a string removing duplicates characters and whitespaces.
 * @AUTHOR SHANTANU KHAN 
 * @WEBSITE http://0code.blogspot.com/  
 */
import java.util.*;
public class PermutationIterative
{
    private char[] S; // INSTANCE VARIABLE
    private int count;
    public PermutationIterative(String Word){ // CONSTRUCTOR
        S=removeInvalid(Word).toCharArray();
        bubbleSort();
    }
    
    private boolean permuteNext()
    {
        int i,j;
        i=S.length-2; // 1. STARTING FROM END FINDING i SUCH THAT S[i]<S[i+1]
        while(i>=0 && S[i]>S[i+1])
            i--;
        if(i<0) // NO MORE PERMUTATIONS POSSIBLE
            return false;
        j=S.length-1; // 2. ITERATING BACK FINDING j S[j]>S[i]
        while((int)S[j]<(int)S[i])
            j--;
        char temp=S[i]; // 3. SWAPPING arr[i] AND arr[j]
        S[i]=S[j];
        S[j]=temp;
        int f=i+1,b=S.length-1; // 4. REVERSING ELEMENTS AFTER i
        while(f<b){
            temp=S[f];
            S[f++]=S[b];
            S[b--]=temp;
        }
        return true;
    }
    
    public void permute(){
        System.out.println(S); // PRINT THE ORIGINAL WORD
        count++; // FOR THE FIRST PERMUTATION
        while(permuteNext()){ // EXECUTION ENDS WITHIN THE permuteNext()
            System.out.println(S);
            count++;
        }
        System.out.println("\nNo. of Permutations : "+count);
    }
    
    private static String removeInvalid(String s){
        String output="";
        for(int i=0;i<s.length();i++){
            if(!Character.isWhitespace(s.charAt(i))&&(output==""||output.indexOf(s.charAt(i))<0))
                output+=s.charAt(i);
        }
        return output;
    }
    
    public void bubbleSort()
    {
        for(int i=S.length-1;i>0;i--){ // NUMBER OF PASSES
            for(int j=0;j<i;j++){        // NUMBER OF COMPARISONS IN EACH PASS
                if(S[j]>S[j+1]){     // IF GREATER, SWAPPING J AND J+1 ELEMENT
                    char temp=S[j];    S[j]=S[j+1];    S[j+1]=temp; // SWAPPING ELEMENTS
                }
            } // END OF COMPARISION (j) LOOP
        } // END OF PASS (i) LOOP
    }
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        System.out.print("Enter the Word : ");
        PermutationIterative obj=new PermutationIterative(sc.nextLine());
        obj.permute();
    }
}

0 comments :

Post a Comment