Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

javascript permutation generator with permutation length parameter

I've seen a few generators out there but they all make a squared matrix. For example, you give it a list of three items and it'll assume the output of the length is also three. However, I'd like to specify the items and the length.

Sound like an easy problem can't believe there isn't a library available for it. Would like to avoid writing this myself if there's a tested library out there. Any suggestions would be great.

Example of what i've found

var list = 'abc';
perms = permutations(list);
//you cannot define the length

Example

var list = 'abc';
var length = 3;

perms = permutations(list,length);

console.log(perms);

/* output
a,a,a
a,b,c
a,b,a
a,c,a
c,a,a
...
*/

I would like to be able to change length and should create permutations accordingly

length = 2

a,a
a,b
b,b
b,a

length = 4

a,a,a,a 
a,a,a,b
....
like image 497
uptownhr Avatar asked Dec 05 '22 06:12

uptownhr


1 Answers

You can imagine the length as representing the number of slots. Each slot has N possibilities, given that N is the number of elements in your initial list. So given three values [1,2,3], you will have a total of 3 x 3 x 3 = 27 permutations.

Here's my attempt. Comments included!

var list = [1,2,3];

var getPermutations = function(list, maxLen) {
    // Copy initial values as arrays
    var perm = list.map(function(val) {
        return [val];
    });
    // Our permutation generator
    var generate = function(perm, maxLen, currLen) {
        // Reached desired length
        if (currLen === maxLen) {
            return perm;
        }
        // For each existing permutation
        for (var i = 0, len = perm.length; i < len; i++) {
            var currPerm = perm.shift();
            // Create new permutation
            for (var k = 0; k < list.length; k++) {
                perm.push(currPerm.concat(list[k]));
            }
        }
        // Recurse
        return generate(perm, maxLen, currLen + 1);
    };
    // Start with size 1 because of initial values
    return generate(perm, maxLen, 1);
};

var res = getPermutations(list, 3);
console.log(res);
console.log(res.length); // 27

fiddle

like image 106
linstantnoodles Avatar answered Dec 09 '22 14:12

linstantnoodles