recursive function works, generative version is wrong

Question

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)]

@Bergi thanks for thinking of that.. but in fact this is not some fumble on enumeration (I added a traditional for loop with output to the op) — roberto tomás
– roberto tomás, Commented Sep 15, 2021 at 23:39

Bergi · Accepted Answer · 2021-09-15 23:35:07Z

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];
        }
      }
    }
  }
}

edited Sep 15, 2021 at 23:35

answered Sep 15, 2021 at 23:29

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

roberto tomás Over a year ago

great job spotting the problem, thank you for this :)

Collectives™ on Stack Overflow

recursive function works, generative version is wrong

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related