powerset<T> function

Iterable<T> powerset<T>(Iterable<Iterable<T>> source, T combinator(T a, T b))

Returns the powerset of the given source using the provided combinator.

The powerset of a set is the set of all possible subsets of the set.

The combinator is a function that combines two elements of the set.

Example:

print(
  powerset({{1}, {2, 3},}, (a, b) => a + b),
); // prints {3, 4}

Implementation

Iterable<T> powerset<T>(
  Iterable<Iterable<T>> source,
  T Function(T a, T b) combinator,
) {
  // Filter out empty sets to simplify logic.
  final input = source.where((e) => e.isNotEmpty);

  if (input.isEmpty) {
    return Iterable.empty();
  } else if (input.length == 1) {
    // Return the first iterable if only one exists.
    return input.first;
  } else {
    // Use expand to create a lazy flattened iterable from the first two sets.
    final firstTwoCombined = input.elementAt(0).expand((a) {
      return input.elementAt(1).map((b) => combinator(a, b));
    });

    // If more sets remain, recursively process them.
    if (input.length > 2) {
      return powerset([firstTwoCombined, ...input.skip(2)], combinator);
    } else {
      return firstTwoCombined;
    }
  }
}