Monday, 16 May 2016

Finding all the permutations of the given String - Java Program

Finding all the permutations of a given String has both a recursive solution and a non-recursive solution. In this post we'll see both kind of solutions.

Recursive is easy to code but a little difficult to visualize where as non-recursive is a little difficult to code but once you know the logic it is easy to visualize what code is doing.

Permutations of a String - Non Recursive

Logic for the non recursive solution is as follows -

  1. First thing to do is to sort the given string in ascending order that is the first permutation so print it.
  2. Now we have to generate all the other permutations until the string is sorted in descending order. That becomes the last permutation to be printed and signals the end of the program.
  3. For every permutation previous permutation becomes the starting point and from there the steps are -
    1. Find the rightmost char in the String which is smaller than the next character.
      As exp. If String is BCDA then you need to scan through the chars, B is smaller than the next char 'C' but remember you have to find the rightmost character and 'C' is also smaller than the next character 'D' that means 'C' is the char you are looking for. Let's call this char as 'CHAR1'.
    2. Second step is to find the ceiling of the 'CHAR1' starting from the index of the 'CHAR1', ceiling here means starting from the index of the 'CHAR1' you have to find the smallest character which is greater than the 'CHAR1'. Let's call this char as 'CHAR2'.
      As exp. If string is BCDAE and C is 'CHAR1' then you are looking for the smallest character with in the String "DAE" which is greater than C. So it should be D so D is 'CHAR2' in this case.
    3. Swap these 2 characters found using Step1 and Step2 i.e. CHAR1 and CHAR2.
    4. In the resultant string take the substring after the index of 'CHAR1' till end and sort it.

Let's see all the steps with an example - If passed String is 'ABCDEF' and at some point the permutation is 'CFADEB' then in order to find the next permutation.

In Step1 it will go through the following combinations to find the 'CHAR1' CFADEB - C-F, F-A, A-D, D-E, E-B So CHAR1 is D.

In Step2 we have to find the smallest char which is greater than D with in the substring EB. So 'CHAR2' is E.

In Step3 - Swapping these will give the String CFAEDB.

In Step 4 - if we use 0 based index then the original index of 'CHAR1' was 3. In String CFAEDB if we take the sub string after index 3 then DB is the resultant string which has to be sorted.

So the end string is CFAEBD and that is the next permutation.

Note that this logic take cares of the duplicate chars too. If you enter "DDDD" as string it will give you only one String "DDDD" as output.

Permutations of a String - Non-recursive Java code

import java.util.Arrays;

public class PermNR {

    public static void main(String[] args) {
        
        permute("ABCDEF");

    }
    
    public static void permute(String str){
        char[] temp = str.toCharArray();
        // Step 1. Sort the string
        Arrays.sort(temp);
        System.out.println("String " + String.valueOf(temp));
        int index = 0;
        int lowest = 0;
        while(true){
            // Step 2. Rightmost char smallest than its neighbour
            for(int i = 0; i < temp.length - 1; i++){
                if(temp[i] < temp[i+1]){
                    lowest = i;
                    
                }
            }
            // index of CHAR1
            index = lowest;
            // Step3. Find the ceiling of the 
            int j = findCeiling(temp, index);
            // Breaking condition at this juncture
            // all permutations are printed
            if(j == index) break;
            
            swap(temp, index, j);
            String a = String.valueOf(temp);
            // Step4. Sort the substring
            char[] b = a.substring(index + 1).toCharArray();
            Arrays.sort(b);
            a = a.substring(0, index + 1) + String.valueOf(b);
            temp = a.toCharArray();
            System.out.println( "String " + String.valueOf(temp));
            //}
        }
        
        
        
    }
    
    /**
     * 
     * @param temp
     * @param index
     * @return
     */
    public static int findCeiling(char[] temp, int index){
        int k = index;
        char test = temp[index];
        while (k < temp.length - 1){
            if(temp[index] < temp[k + 1]){
                index = k + 1;
                break;
            }
            k++;
        }
        k = index;
        while (k < temp.length - 1){
            if((temp[index] > temp[k + 1]) && (temp[k + 1] > test)){
                index = k + 1;
            }
            k++;
        }
        return index;
    }
    
    /**
     * Method used for swapping the char
     * @param str
     * @param i
     * @param j
     */
    private static void swap(char[] str, int i, int j){
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
}

Permutations of a String - Recursive

Here the method will call itself, keeping portion of a string as constant. A base condition is also needed which is when string length is 0.

public class PermDemo {

    public static void main(String[] args) {
        permutation("abcde");

    }
    public static void permutation(String str) {
        permutation("", str);
    }
    // recursive method
    private static void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0){
            System.out.println(prefix);
        }
        else {
            for (int i  = 0;  i < n;  i++){
                //System.out.println("prefix " + prefix + " i " + i);
                 permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
            }
        }
    }
}

Source for recursive code is : http://introcs.cs.princeton.edu/java/23recursion/Permutations.java.html

Explanation

After first base point when n becomes 0 we'll have these 3 calls. Note that for all these calls i will be 0 as permutation method is called again.

permutation("a", "bc");
permutation("ab", "c");
permutation("abc", "");

Since method calls follow stack data structure so FIFO (First In First Out) will be followed. Let's lay out our method calls in that way.

permutation("abc", "");
permutation("ab", "c");
permutation("a", "bc");

Now first call will print the String "abc", second call permutation("ab", "c") will go in the for loop with i = 1 and n = 1 so it will come out and won’t print anything as for loop has condition (i < n). Third call permutation(“a”, “bc”); will go in the for loop with i =1 and n=2. Which will lead to following calls again following that same pattern as explained above it will print acb.

Permutation("a", "bc");
Permutation("ac", "b");
Permutation("acb", "");

That's all for this topic How to find all the permutations of the given String. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Check whether a given String/Number is a palindrome or not
  2. How to find the longest palindrome in the given String
  3. How to add double quotes to a String
  4. Print odd-even numbers using threads and semaphore
  5. Print odd-even numbers using threads and wait-notify
  6. Count number of words in a String

You may also like -

>>>Go to Java Programs page

No comments:

Post a Comment