Permutations (Recursive)176 views

AlgoPill 
 function permutations(str){
    // util function swap
    function swap(ar,a,b){
        var tmp = ar[a];
        ar[a] = ar[b];
        ar[b] = tmp;
    } 
    /**
     * recursive function
     * @param {Array} buff output buffer
     * @param {Array} arr representing elements of input string
     * @param {number} start
     * @param {number} end
     */ 
    function permute(buff,arr,start,end){
        var i,range = end-start;
        if(end-start==1){
            buff.push(arr.join("")); // output
        } else {
            for(i=0;i<range;i++){
                swap(arr,start,start+i);
                permute(buff,arr,start+1,end);
                swap(arr,start,start+i);
            }
        }
    }
    
    
    var buff = [];
    permute(buff,str.split(""),0,str.length);
    return buff;
}

Problem Statement: Given a string find all permutations of string. It can be assumed that string does not had repeated characters.
Solution :
This is a simple algorithm for generating permutations. It uses a recursive construction. There are two points to be understood in order to this understand this algorithm
1. The recursive construction
consider finding all permutions of the string “abcd”, all permutations of this string are union of following
permutaion(“abcd”) =
1. “a” + permutations(“bcd”)
2 “b” + permutations(“acd”)
3 “c” + permutaions(“bad”)
4 “d” + permutations(“bca”);
where “+” is concatenation operator
the permutation of “bcd”, “acd”,”bad”,”bca” can be calculated similarly.

2. The swap part
as noted above in order to generate permutations we place all characters one by at position 0. The first case where “a” is at the first place requires not change in remaining string. In all other cases we pull out remaining characters one by one from remaining string and replace it with “a”. Also the second swap in code after the call of permute, restores the string back to original string so that we can proceed with the next character replacement.

This solution does NOT generate permutations in lexicographic order and it does NOT take care of repeated characters.

Post a Comment

You must be logged in to post a comment.