Permutation Iterative : Java : BlueJ

Permutation Iterative : Java : BlueJ

Objective :

The class PermutationIterative computes all the Unique Permutations of a string removing duplicates characters and white spaces. The Algorithm is a simple one ! All the permutations are  printed in lexicographic form.

Here the Original string is validated (duplicate and white spaces are removed) and sorted using bubble sort technique. It finds the next Permutation of a given string by the following set of rules:

• Start scanning the string from the end such that arr[i] < arr[i+1]. Here it is advisable to start counting from S.length-1.
• If i occurs to be less than 0, no more permutations are possible.
• Start scanning from end such that arr[j]>arr[i].
• Swap the elements arr[i] and arr[j]
• reverse the elements after arr[i].
• Now you have the next permutation and run a loop until the function return false.

The program will automatically run !n times and all the inputs will be in lexicographic form. This program is faster and memory efficient and can be easily applied in other languages.

BlueJ Program Screenshot :

Java Program Source Code :

/**
 * The class PermutationIterative computes all the Unique Permutations
 * of a string removing duplicates characters and whitespaces.
 * @AUTHOR SHANTANU KHAN 
 * @DATE  
 */
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();