While trying to solve scribd’s bot puzzle, I wanted to generate permutations of a passed in array.

Say the array has 1,2,3. What are the permutations possible?
321
231
213
312
132
123

If you have to do it with pen and paper, how would you do it?

Say you are currently processing 1. What are the permutations of 1? 1 right?

Now, you are processing 2. What are the permutations of 1 and 2? 12 and 21 right? How did you arrive at this? You added 2 to the beginning of 1 and end of 1.

Now, you are processing 3. What are the previous two permutations that we have? 12 and 21. Now we have to fit 3. What do we do? Add 3 to the beginning and end of both, i.e 312 123 and 321 213. Along with the ends, we also add 3 in between the digits, i.e 132 and 231. There you go, you have all permutations of 1,2 and 3.

Below code extends this idea to any number of elements.

function getAllPermutations(ary) {
    var len = ary.length;
    //console.log('Length:' + len);
    var i = 0, j = 0, k = 0;
    var elem, containerElem;
    //console.dir(ary[0]);
    var container = [[ary[0]]];
    var copied;

    /*
    console.log('------------>------------');
    for (i = 0; i < len; ++i) {
        elem = ary[i];
        console.dir(elem);
    }
    console.log('------------>------------');
    */

    for (i = 1; i < len; ++i) {
        //console.log('I is:' + i);
        elem = ary[i];
        copied = copy(container);
        container = [];
        for (j = 0; j < copied.length; ++j) {
            containerElem = copied[j];
            ret = helper(elem, containerElem);

            for (k = 0; k < ret.length; ++k) {
                container.push(ret[k]);
            }
        }
    }

    return container;

    function helper(elem, ary) {
        /*
        console.log('In helper start');
        console.log('Elem is:');
        console.dir(elem);
        console.log('Ary is:');
        console.dir(ary);
        */
        var len = ary.length;
        var elem;

        var container = [];
        var copied;
        for (var i = 0; i < len; ++i) {
            copied = copy(ary);        
            copied.splice(i, 0, elem);
            container.push(copied);
        }
        copied = copy(ary);        
        copied.push(elem);
        container.push(copied);
        /*
        console.log('Result is:');
        console.dir(container);
        console.log('In helper end');
        */
        return container;
    }
}

function copy(ary) {
    var copied = [];
    var len = ary.length;

    for (var i = 0; i < len; ++i) {
        copied.push(ary[i]);
    }
    
    return copied;
}
Advertisements