Skip to content

Instantly share code, notes, and snippets.

@hildjj
Created January 19, 2021 20:38
Show Gist options
  • Save hildjj/082bf5104006fc8cf97f92324b2607a8 to your computer and use it in GitHub Desktop.
Save hildjj/082bf5104006fc8cf97f92324b2607a8 to your computer and use it in GitHub Desktop.
time node 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment