Skip to content

Instantly share code, notes, and snippets.

@vladignatyev
Created February 29, 2020 19:28
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save vladignatyev/7494a7100a2971b80de9ebb200f9de2c to your computer and use it in GitHub Desktop.
Save vladignatyev/7494a7100a2971b80de9ebb200f9de2c to your computer and use it in GitHub Desktop.
Combinatorics: Good Power Set implementation in ECMAScript
function *powerSet(sourceSet) {
function product(ones, sourceSet) {
let l = ones.length;
let out = new Array(l);
for (var i = 0; i < l; i++) {
out[i] = sourceSet[ones[i]]
}
return out;
}
function getMostSignificant(ones, sourceSet) {
let k = ones.length - 1;
const sourceSetLen = sourceSet.length;
const onesLen = ones.length;
while (ones[k] == (sourceSetLen - 1) - (onesLen - 1 - k)) k--;
return k;
}
// trivial case
yield [];
let l = sourceSet.length;
for (var setlen = 1; setlen <= l; setlen++) {
let ones = new Array(setlen);
for (var i = 0; i < setlen; i++) ones[i] = i;
yield product(ones, sourceSet);
if (setlen == l) return;
const lastDigit = setlen - 1;
while ('💃🏾') {
ones[lastDigit] = ones[lastDigit] + 1;
if (ones[lastDigit] > l - 1) {
ones[lastDigit] = l - 1;
const k = getMostSignificant(ones, sourceSet);
if (k == -1) break;
ones[k] = ones[k] + 1
for (var m = k + 1; m < setlen; m++) ones[m] = ones[m-1] + 1;
}
yield product(ones, sourceSet);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment