Last active
November 21, 2022 08:13
-
-
Save rakeshta/ecca304c3b5a4deafce328813dd01b36 to your computer and use it in GitHub Desktop.
A utility function to enumerate all subsets of a given set
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
/** | |
* Counts the number of `true` (or `1`) bits in the given integer. | |
* | |
* @remarks This is an efficient algorithm that works for 32-bit integers only. | |
* | |
* @param i The integer to count the number of `true` bits in. | |
* @returns The number of `true` bits in the given integer. | |
* | |
* @see {@link https://stackoverflow.com/a/109025/11236} for the source of this algorithm. | |
* @see {@link https://en.wikipedia.org/wiki/Hamming_weight} for explanations & other efficient implementations. | |
*/ | |
export function trueBitCount(i: number): number { | |
i = i - ((i >> 1) & 0x55555555); | |
i = (i & 0x33333333) + ((i >> 2) & 0x33333333); | |
i = (i + (i >> 4)) & 0x0f0f0f0f; | |
return (i * 0x01010101) >> 24; | |
} | |
/** | |
* An efficient algorithm to enumerate all subsets of a given set of items. The given subset is allowed to have | |
* duplicate items. All that matters for inclusion is their unique position in the given set. | |
* | |
* @param {T[]} set The source superset. | |
* @param {number | undefined} minLength Optional parameter to limit the minimum number of items in an included subset. | |
* @param {number | undefined} maxLength Optional parameter to limit the maximum number of items in an included subset. | |
* @returns {T[][]} An array of all subsets of the given set (that match the length limits if given). | |
*/ | |
export function enumerateSubsets<T>(set: T[], minLength?: number, maxLength?: number): T[][] { | |
const arr = Array.from(set); | |
const subsets: T[][] = []; | |
// utility function to test if a given index position matches the give length limits | |
const isInclude = (() => { | |
// include all if limits not provided | |
if (minLength === undefined && maxLength === undefined) { | |
return () => true; | |
} | |
// filter out sets that are outside the limits | |
const min = minLength ?? 0; | |
const max = maxLength ?? arr.length; | |
return (i: number): boolean => { | |
const count = trueBitCount(i); | |
return count >= min && count <= max; | |
}; | |
})(); | |
/* | |
* How this works: | |
* | |
* Imagine counting in binary from 0 to 2^n - 1, where each bit position represents whether | |
* the corresponding item in the set is included in the subset. For example, for a set [3, 7, 9, 8] | |
* index position 0b1010 (decimal 10) represents the subset [3, 9]. | |
* | |
* To filter out sets that are outside the limits, we just have to count the number of `1`s in the | |
* index position. If it's outside the limits, we skip it. | |
*/ | |
const max = 2 ** set.length; | |
for (let i = 0; i < max; i++) { | |
// skip if the set length is outside the limits | |
if (!isInclude(i)) { | |
continue; | |
} | |
// collect values from the original set at positions where the bit is `1`. | |
const subset: T[] = []; | |
let j = i; | |
let k = 0; | |
while (j > 0) { | |
if (j & 1) { | |
subset.push(arr[k]); | |
} | |
j >>= 1; | |
k++; | |
} | |
subsets.push(subset); | |
} | |
return subsets; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment