Lexicographic Permutations (Iterative)901 views

AlgoPill 
 function lexicographicPermutations(str){
    function swap(ar,a,b){
        var tmp = ar[a];
        ar[a] = ar[b];
        ar[b] = tmp;
    }
    
    function next(mstr){
        var i = mstr.length - 2;
        /* Find the largest i */
        while ((i >= 0) && (mstr[i] > mstr[i + 1])){
            --i;
        }
        if (i < 0)
            return true;
        var k = mstr.length - 1;
        /* Find the largest element after vi but not larger than vi */
        while (mstr[i] > mstr[k]){
            --k;
        }
        swap(mstr,i,k);
        var j;
        k = 0;
          /* Swap the last n - i elements. */
        for (j = i + 1; j < Math.floor((mstr.length + i) / 2 + 1); ++j, ++k){
            swap(mstr,j, mstr.length - k - 1);
        }
        return false;
    }
    var permutations = [],
        mstr = str.split(''); // mutable string
        permutations.push(mstr.join("")); // add the given
        var done = true;
    do {
        if (!(done = next(mstr))){
        permutations.push(mstr.join(""));  /* P3 */
        }
    } while (!done);
        
    return permutations;
}

Problem Statement : Given a string of characters generate all permutations of string in lexicographic order.
Solution: This algorithm has been taken from http://compprog.wordpress.com/2007/10/08/generating-permutations-2/

This algorithm will generate all permutations of a string in lexicographic using an iterative algorithm. The input string to this algorithm must have all the characters in lexicographic order. For example, if we want to generate permutations of “bcad” string. Then input string should be “abcd” because a<b<c<d. This algorithm cannot handle duplicate characters so all characters must be unique.

The key routine of this algorithm is the routine “next”. Given a permutation “next” routine will find another permutation that comes next in lexicographic order.  This algorithm uses “next” to generate next permutation iteratively until all the characters in the string are in reverse lexicographic order. For example give “abcd” string , it will generate all permutaion until we reach “dcba” since this is the last permutation in lexicographic order. Now the working of “next” routine  is explained below with an example.

consider a permutaion of “abcdefghij”      p1  =  ”chdafijgeb”

now lets find out next permutation in lexicographic order.

Step1. Starting with last char i.e. ‘b’ , decrease  the counter as long as characters are in increasing order and find first character that breaks this trend. In this example we started ‘b’, thus ‘e’>’b',  ’g'>’e’  ,  ’j'>’e',  but ‘i’<’j’ , thus the character that break this trend is ‘i’.

Step2 . Find the largest element starting from last element i.e. ‘b’ such that it is smaller than the element found in last step i.e. ‘i’. ‘b’<’i', ‘e’<’i',’g'<’i',’j’ > ‘i’ , therefore the character is ‘g’;

Step 3  Now swap ‘g’ and ‘i’; after this step we get    p1′  =  ”chdafgjieb”;

Step 4 now reverse the string starting after ‘g’ to the end. which gives us p1”  = “chdafgbeij”, this gives us smallest string that is larger than the input string and thus next in the lexicographic order

Post a Comment

You must be logged in to post a comment.