1

I have troubles to make this work. My understanding of this algorithm (based on wikipedia explanation) is that it should work like I did in code below. But something isn't working. In case with 2, 3, 4 digits or letters everything works well but in case with more digits or letters the algorithm doesn't work.

Any ideas what is wrong here?

Here is the code:

//swap two letters at the given index
String.prototype.swapLetters = function(i){
    var a = this.split("");
    var temp = this[i];
    a[i]=a[i+1];
    a[i+1]=temp;
    return a.join("");
}

//get all posible combinations for given string
function combs(n){
    if(n === 0){
        return 1;
    } else {
        return n*(combs(n-1));
    }
}



function permAlone(str) {
    var reg = new RegExp(/(\w)\1+/);
    var c = 0;
//the point of this function is to implement Steinhaus–Johnson–Trotter algorithm 
// to list all permutations. The algorithm should work like this: if we have 1234
// 1. 2134; -> 2. 2314; -> 3. 2341;
// now is break switch first two letters so:
// 4. 3241; 
// then proced is oposite direction 
// 5. 3214; -> 3124;...
function permutations(str, p, n, b, perms){
    var index = p-n;
    var len = str.length-2;
    console.log(str);
    if(perms===0){
        return;
    }
    //if p is less then or equal and b is zStart then increase p by 1
    //if p is equal to len do not increment p just call function with b===zBreak (call function to swich first two letters)
    if(p <= len && b==="zStart"){
        if(p === len){
            b = "zBreak";
        } else {
            p = p+1;
        }
    return permutations(str.swapLetters(index), p, n, b, perms-1);
    }
    //if n is less then or equal and b is lStart then increase n by 1
    //if n is equal to len do not increment n just call function with b===lBreak (call function to swich first last two letters)
    if (n <= len && b==="lStart"){
        if(n === len){
            b = "lBreak";
        } else {
            n = n+1;
        }
    return permutations(str.swapLetters(index), p, n, b, perms-1);
    } 
    //if b is zBreak swap first two letters and set b to be lStart because
    //next break should swap last two letters 
    if(b==="zBreak"){
        return permutations(str.swapLetters(0), p, n, "lStart", perms-1);
    } else if(b==="lBreak"){
        return permutations(str.swapLetters(len), 0, 0, "zStart", perms-1);
    }
    return permutations(str.swapLetters(index), p, n, b, perms-1);
}
    permutations(str, 0, 0, "zStart", combs(str.length));

}

permAlone('1234');
Enis Jasarovic
  • 125
  • 1
  • 8

0 Answers0