this recursive functions works just fine to get combinations of values from an array:
function combinations(set, k) {
if (k > set.length || k <= 0) return []
if (k === set.length) return [set]
if (k === 1) return set.map(x => [x])
return set.reduce((p, c, i) => {
combinations(set.slice(i + 1), k - 1).forEach(tailArray =>
p.push([c].concat(tailArray)),
)
return p
}, [])
}
I tried to convert that to a generative version:
function* combinations(set, k) {
if (k > set.length || k <= 0) yield []
if (k === set.length) yield set
if (k === 1) yield* set.map(x => [x])
for (let i in set) {
for (const next of combinations(set.slice(+i + 1), k - 1)) {
yield [set[i]].concat(next)
}
}
return
}
however this returns far more results than it should, and they are not all the right length
function timeFn(fn){
const pre = performance.now()
const r = fn()
const post = performance.now()
console.log('time', (post - pre)/1000 , 's')
return r
}
timeFn(()=> [...combinations([...Array(4)].map((_,i)=>i+1), 3)])
VM2045:5 time 0.00009999999403953553 s
(20) [Array(3), Array(3), Array(3), Array(4), Array(3), Array(3), Array(3), Array(3), Array(3), Array(3), Array(2), Array(3), Array(3), Array(3), Array(3), Array(3), Array(2), Array(1), Array(2), Array(1)]
sadly, its not just for...in:
function* combinations(set, k) {
if (k > set.length || k <= 0) yield []
if (k === set.length) yield set
if (k === 1) yield* set.map(x => [x])
for (let i=0,lim=set.length; i<lim; i++) {
for (const next of combinations(set.slice(i + 1), k - 1)) {
yield [set[i]].concat(next)
}
}
return
}
undefined
timeFn(()=> [...combinations([...Array(4)].map((_,i)=>i+1), 3)])
VM2045:5 time 0.00020000000298023223 s
(20) [Array(3), Array(3), Array(3), Array(4), Array(3), Array(3), Array(3), Array(3), Array(3), Array(3), Array(2), Array(3), Array(3), Array(3), Array(3), Array(3), Array(2), Array(1), Array(2), Array(1)]
You have not correctly converted the base cases to the generator version:
if (k > set.length || k <= 0) return []
if (k === set.length) return [set]
if (k === 1) return set.map(x => [x])
Notice that these return, while your generator function carries on, emitting all of them.
function* combinations(set, k) {
if (k > set.length || k <= 0) {
// notice this yields nothing
return
}
if (k === set.length) {
yield set
return
}
if (k === 1) {
yield* set.map(x => [x])
return
}
for (let i=0; i<set.length; i++) {
for (const next of combinations(set.slice(i + 1), k - 1)) {
yield [set[i]].concat(next)
}
}
}
Btw, k === set.length and k === 1 are not base cases but (unnecessary) optimisations, and your functions don't work correctly for k === 0 - that should generate one empty array. Better:
function* combinations(set, k) {
if (k >= 0 && k <= set.length) {
if (k == 0) {
yield [];
} else {
for (const [i, v] of set.entries())
for (const next of combinations(set.slice(i + 1), k - 1)) {
yield [v, ...next];
}
}
}
}
}