Created
February 29, 2020 19:28
-
-
Save vladignatyev/7494a7100a2971b80de9ebb200f9de2c to your computer and use it in GitHub Desktop.
Combinatorics: Good Power Set implementation in ECMAScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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