Permutations (recursive) 2226 views

AlgoPill 
 function permutationsRecursive(str){
    function rotate(ar,a,b){
      var i,save = ar[b-1];
      for(i=b-1;i>a;i--){
          ar[i]=ar[i-1];
      }
      ar[a]=save;
    }
    function permute(buff,arr,start,end){
        var i,range = end-start;
        if(end-start==1){
            buff.push(arr.join(""));
        } else {
            for(i=0;i<range;i++){
                rotate(arr,start,end);
                permute(buff,arr,start+1,end);
            }
        }
    }
    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. “d” + permutations(“abc”)
2 “c” + permutations(“dab”)
3 “b” + permutaions(“cda”)
4 “a” + permutations(“bcd”);
where “+” is concatenation operator
the permutation of “abc”, “dab”,”cda”,”bcd” can be calculated similarly.

2. Rotate part
as noted above in order to generate permutations we place all characters one by at position 0. The first case where “d” is moved to first place by rotating the string such that every character’s index is increased by one and last character i.e “d” is moved to first. At second step characters are moved by one place which bring “c” in first place. This is done four times since the length of string is four.

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.