time node js-itertools.js

js-itertools.js

'use strict'

/**
  * Is the given thing iterable?
  *
  * @static
  * @param {any} g - the thing to check
  * @returns {boolean} - true if `g` looks like an iterable
  */
function isIterable(g) {
  return g &&
    (typeof g === 'object') &&
    (g[Symbol.iterator])
}

// BELOW lifted from https://github.com/aureooms/js-itertools,
// removed need for regenerator runtime, modernized, and cleaned up.
// ----------

/**
  * Like Python's range(), generate a series of numbers.
  *
  * @static
  * @param {number} start - the starting point
  * @param {number} [stop] - the ending point, which isn't reached
  * @param {number} [step=1] - how much to add each time, may be negative
  * @yields {number} - each number in the range
  */
function *range(start, stop, step=1) {
  if (stop == null) {
    [start, stop] = [0, start]
  }
  if (step < 0) {
    while (start > stop) {
      yield start
      start += step
    }
  } else {
    while (start < stop) {
      yield start
      start += step
    }
  }
}

/**
  * Pick some properties or array values out of `source`.
  *
  * @static
  * @param {Object|Array<any>|Iterable<any>} source - thing to select from
  * @param {Iterable<number|string>} it - the indexes or property names
  * @yields {any} - the selected property
  */
function *pick(source, it) {
  if (isIterable(source)) {
    // `it` might be out of order, and so might `source`.
    source = [...source]
  }
  for (const i of it) {
    yield source[i]
  }
}

/**
  * Combinations of a series, r at a time
  *
  * @static
  * @param {Iterable} iterable - the series to iterate.
  * @param {number} r - How many of the series to use in each combination?
  * @yields {Array<any>} - each combination
  */
function *combinations(iterable, r) {
  const pool = Array.isArray(iterable) ? iterable : [...iterable]
  const length = pool.length

  if (r > length) {
    return
  }

  const indices = [...range(r)]
  yield [...pick(pool, indices)]

  while (true) {
    let i = r - 1
    while (true) {
      if (i < 0) {
        return
      }
  
      if (indices[i] !== i + length - r) {
        let pivot = ++indices[i]
        for (++i; i < r; ++i) {
          indices[i] = ++pivot
        }
        break
      }
      i--
    }
  
    yield [...pick(pool, indices)]
  }
}

// ------ actual example --------
const a = Array.from(new Array(200), (_, i) => i)
let tot = 0
for (const [x, y, z] of combinations(a, 3)) {
  tot += x*y*z
}
console.log(tot)

// 1287230505000
// node js-itertools.js  0.70s user 0.03s system 97% cpu 0.749 total