A utility function to enumerate all subsets of a given set

enumerate-subsets.ts

/**
 * 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;
}