Permutation with max length parameter

Question

I'm writing an function to create all possible permutation with max length limitation, and each item in array can only be used once.

The original permutation code as follows:

function permutations(list)
{
    // Empty list has one permutation
    if (list.length == 0)
        return [[]];

    let result = [];

    for (let i=0; i<list.length; i++)
    {
        // Clone list (kind of)
        let copy = Object.create(list);

        // Cut one element from list
        let head = copy.splice(i, 1);

        // Permute rest of list
        let rest = permutations(copy);

        // Add head to each permutation of rest of list
        for (let j=0; j<rest.length; j++)
        {
            let next = head.concat(rest[j]);
            result.push(next);
        }
    }

    return result;
}

How best to add this max length parameter to create unique combination result? I added maxLength. But in recursion stuck on where to best implement this parameter.

Just add it as param to your function and pass it along if you call it again or make a "global" variable — kevinSpaceyIsKeyserSöze, Dec 17 '19 at 07:55
Does this answer your question? [javascript permutation generator with permutation length parameter](https://stackoverflow.com/questions/23305747/javascript-permutation-generator-with-permutation-length-parameter) — ChatterOne, Dec 17 '19 at 08:40

score 4 · Answer 1 · answered Dec 17 '19 at 09:05

From a minimalist point of view, stop the recursion not when you have shrinked list from its size but when maxLength element have been taken from the list.

function permutations(list, maxLength)
{
    // Empty list has one permutation
    if (maxLength == 0)
        return [[]];

    let result = [];

    for (let i=0; i<list.length; i++)
    {
        // Clone list (kind of)
        let copy = Object.create(list);

        // Cut one element from list
        let head = copy.splice(i, 1);

        // Permute rest of list
        let rest = permutations(copy, maxLength-1);

        // Add head to each permutation of rest of list
        for (let j=0; j<rest.length; j++)
        {
            let next = head.concat(rest[j]);
            result.push(next);
        }
    }

    return result;
}
const maxLength = 4
console.time('by cp')
var r = permutations([1, 2, 3, 4, 5, 6], maxLength)
console.timeEnd('by cp')
console.log(r)

However, a similar approach but slightly more performant is to avoid copying the array for every "try" and only copy it when a solution is found

function permutations2(iList, maxLength)
{
    const cur = Array(maxLength)
    const results = []
    function rec(list, depth = 0) {
        if (depth == maxLength) {
            return results.push(cur.slice(0))
        }
        for (let i = 0; i < list.length; ++i) {
            cur[depth] = list.splice(i, 1)[0]
            rec(list, depth + 1)
            list.splice(i, 0, cur[depth])
        }
    }
    rec(iList)
    return results;
}
console.time('cp on solution')
var r = permutations2([1, 2, 3, 4, 5, 6], 4)
console.timeEnd('cp on solution')
console.log(r)

Permutation with max length parameter

1 Answers1

Linked