TypeScript implementation of combination without replacement (i.e. Heap's Algorithm)

combinateWithoutReplacement.ts

export function* combinateWithoutReplacement<T>(candidates: T[]) {
  const indices = candidates.map((_, i) => i)

  yield indices.map((i) => candidates[i])

  const c = indices.map(() => 0)
  let i = 1
  while (i < indices.length) {
    if (c[i] < i) {
      if (i % 2 === 0) {
        swap(indices, 0, i)
      } else {
        swap(indices, c[i], i)
      }

      yield indices.map((i) => candidates[i])

      c[i] += 1
      i = 1
    } else {
      c[i] = 0
      i += 1
    }
  }
}

function swap<T>(list: T[], a: number, b: number) {
  const t = list[a]
  list[a] = list[b]
  list[b] = t
}

Direct porting of Heap's Algorithm from wikipedia without recursion. If you're interested how and why it works, please see wikipedia page. It's pretty complicated.

• Input array doesn't changed thanks to indices inner array.
• Every generated arrays are independent, but elements inside of them are not. Be careful when you do some mutation.