TypeScript implementation of permutation of given elements with specific length.

permutation.ts

function* permutate<T>(domain: T[], length: number) {
  function* recurse(stack: T[] = [], depth: number = 0): Generator<T[]> {
    if (depth >= length) {
      yield stack.slice()
      return
    }

    for (const element of domain) {
      stack[depth] = element
      yield* recurse(stack, depth + 1)
    }
  }

  yield* recurse()
}

Example

It generates total 2^n unique (unless domain has duplicated elements) with domain of length n.

• Generation order is lexiographic.
• Every generated arrays are independent objects

console.log([...permutate([0, 1], 3)])

// log followings
// [
//   [0, 0, 0],
//   [0, 0, 1],
//   [0, 1, 0],
//   [0, 1, 1],
//   [1, 0, 0],
//   [1, 0, 1],
//   [1, 1, 0],
//   [1, 1, 1],
// ]

Mutability

Note that this never clone given elements in domain. If you're handling mutable elements, change line 4 as followings:

yield stack.map(element => element.clone())