How to turn a permutations function into a lazy generator?

Matan 0
Viewed 51

I am trying to get all of the permutations of an array, one permutation at time, using a generator.

This is the original code (which works as intended and returns an array of permutations), and below is my attempt to change it:

function permutations(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
    }

My code, which returns nothing:

function* permutations2(iList, maxLength) {
    const cur = Array(maxLength)

    function* rec(list, depth = 0) {
        if (depth === maxLength) {
            yield 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])
        }
    }
    yield rec(iList)
 }

For example, for print(permutations2([1, 2, 3], 2)) I want to get

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

However with the original code I am getting an array of the permutations:

[[1, 2],
[1, 3],
[2, 1],
[2, 3],
[3, 1],
[3, 2]]

I would be grateful to understand why my code is not working, and how to fix it. Thanks!

generator permutation javascript
2 Answers

A lazy generator will take some more work.

Instead of returning your results now, you use yield* to yield all the results that will come forth from rec.

Now rec is also a generator function.

And in a similar manner, instead of return and adding onto our results array, we yield the result.

Something you need to change here is adding the else, because yield does not stop the rest of the function from executing. It's only a pause. That's why we need else to make sure that this code does not execute after we yield.

Inside the else, like above, whenever we call rec, we need to yield the results of rec as well.

function* permutations(iList, maxLength) {
    const cur = Array(maxLength)

    function* rec(list, depth = 0) {
        if (depth === maxLength) {
            yield cur.slice(0);
        } else {
            for (let i = 0; i < list.length; ++i) {
                cur[depth] = list.splice(i, 1)[0];

                yield* rec(list, depth + 1);

                list.splice(i, 0, cur[depth])
            }
        }
    }

    yield* rec(iList);
}

console.log([...permutations([1, 2, 3], 2)]);

This seems to produce the same results but it is lazy now.

caTS0

This is actually all the change you need, generator function, then yield* instead of return.

function* permutations(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);
    yield* results;
}

console.log([...permutations([1, 2, 3], 2)]);

Note that this creates a generator that is not lazy. It computes all of the values beforehand and then yields them all.

yield* is a short way to yield all elements of an iterable or another generator.

caTS0
Related