Javascript generator function does not seem to be called

Question

I have written the following Javascript function. It is supposed to return all the unique permutations (including partial permutations) of the elements of the input array; it is coded as a generator (introduced by function* and returning values using yield), so that the values are evaluated lazily on demand.

function* permute(arr) {
    if (arr.length == 1)
        yield arr
    else if (arr.length) {
        for (let i of arr) {
            const value = arr[i]
            if (arr.indexOf(value) == i) {
                yield [value]
                const others = arr.slice(0, i).concat(arr.slice(i+1))
                for (let perm of permute(others))
                    yield [value, ...perm]
            }
        }
    }
}

To test it, I used the following Jest unit test:

describe("Permute tests", () => {
    test("No duplicates", () => {
        const input = "abc".split("")
        const expected = "a ab abc ac acb b ba bac bc bca c ca cab cb cba"
            .split(" ")
        for (let x of permute(input))
            expect(x.join("")).toBe(expected.shift())
        expect(expected.length).toBe(0)
    })
})

But when I run this, it doesn't give the expected results. The test fails at the last line because expected.length is not zero, it is 15 as no results from the generator have been processed. And this is borne out by the fact that if I put a breakpoint on the first statement in the generator function, it is not hit; it seems that next() is never called on the generator.

I have written other generators, and successfully tested them, but this one consistently doesn't work. What am I doing wrong?

Environment: NodeJS 14.16.0 and npm 7.10.0 on Windows 10 (or Ubuntu 20.04); Jest 26.6.3.

for (let i of arr) is iterating the array elements - not its indexes. But then you index arr on i. — IAmDranged, Apr 19 '21 at 15:22
Thank you, yes that is correct. I realised that, and once I changed it it does produce output. Not exactly the output I am expecting, but it is better than before. — Jeremy Hicks, Apr 20 '21 at 14:18
I've just realised that the reason why it was not producing the output I expected is that `for (let i in arr)` does not iterate over the array indices as I reasonably expected; it iterates over the array indices **converted to strings**. Therefore, when (for example) processing the second element of a three-element array, the line `const others = arr.slice(0, i).concat(arr.slice(i+1))` doesn't create an array containing elements 0 and 2 as I expected; it creates one containing elements 0 and 11 - and 11 doesn't exist, so that slice is empty and the array only contains element 0. — Jeremy Hicks, Apr 21 '21 at 09:30

score 0 · Answer 1 · edited Apr 19 '21 at 15:37

Your code seems to have some issue. it doesn't call recursively. you can check this link Recursive Generators in JavaScript

I tried below one it produces with same logic unique characters

function* permute(arr) {
    if (arr.length == 1)
        yield arr
    else if (arr.length) {      
        for (i=0; i<arr.length; i++) {          
            const value = arr[i]            
            if (arr.indexOf(value) == i) {              
                //yield [value]                
                const others = arr.slice(0, i).concat(arr.slice(i+1))                     
                for (let perm of permute(others))                   
                    yield [value, ...perm]
            }
        }
    }
}
const p = permute("abc".split(""));
console.log(p.next().value)

It *does* call recursively (`for (let perm of permute(others)`).. But as @IamDranged pointed out, I was iterating over the array using a for...of loop when I should have used for...in. Your alternative code worked because you used a more conventional for loop. Thanks anyway for taking the time to consider my problem. — Jeremy Hicks, Apr 20 '21 at 14:20

Jeremy Hicks · Answer 2 · 2021-04-21T11:51:34.617

Thanks to those who have contributed answers; my code is now working. There were two problems, both relating to the way I was iterating over the array.

The first problem was that I was saying for (let i of arr), which iterates over the values, not the indices; and I was then trying to use i to index into arr.
The second problem was that I changed it to for (let i in arr), which iterates over the indices, but treats them as strings, not numbers. Therefore, in the line const others = arr.slice(0, i).concat(arr.slice(i+1)), the expression i+1 didn't return a number that is one more than i, but a number that is the result of concatenating i and 1: that is, the equivalent of saying i*10+1. In order to overcome this, I can either use a conventional for loop instead of a for...in loop, or change the expression i+1 to i*1+1. I think I prefer the former.

The amended version of the function, which works fine, is:

function* permute(arr) {
    if (arr.length == 1)
        yield arr
    else if (arr.length) {
        for (let i = 0; i < arr.length; i++) {
            const value = arr[i]
            if (arr.indexOf(value) == i) {
                yield [value]
                const others = arr.slice(0, i).concat(arr.slice(i+1))
                for (const perm of permute(others))
                    yield [value, ...perm]
            }
        }
    }
}

Javascript generator function does not seem to be called

2 Answers2