How to find all subsets of a set in Dart?

Question

I need to get all possible subsets of an array.

Say I have this:

<int>[1, 2, 3]

How do I get this?

[], [1], [2], [3],[1, 2], [2, 3], [1, 3], [1, 2, 3]

I am interested in all subsets. For subsets of specific length, refer to the following questions: How to find all subsets of a set in JavaScript?

Answer 1

Here is my take on it, with only native function as in your link:

List getAllSubsets(List l) => l.fold<List>([[]], (subLists, element) {
      return subLists
          .map((subList) => [
                subList,
                subList + [element]
              ])
          .expand((element) => element)
          .toList();
    });

If you want a specific size:

List getSizedSubsets(List l, int size) =>
    getAllSubsets(l).where((element) => element.length == size).toList();

Answer 2

I'd probably go with something simple like:

Iterable<Set<E>> subsets<E>(Set<E> elements) sync* {
  if (elements.length >= 32) {
    // Otherwise there'll be more than 2^32 subsets. And bitops will overflow in JS.
    throw ArgumentError.value(elements, "elements", "must have less than 32 elements");
  }
  var list = [...elements];
  var subsetCount = 1 << list.length;
  for (var i = 0; i < subsetCount; i++) {
    yield {
        for (var j = 0, bit = 1; j < elements.length; j++, bit <<= 1) 
            if (i & bit != 0) list[j]
    };
  }
}

Another approach is to only have one set, and then update it iteratively to contain different elements. It's possible to go through all the sets doing only single-element changes on each step (using Gray-code):

/// Iterates a set through all combinations of its elements.
///
/// Adds and removes elements from [set] to make it iterate through all
/// possible combinations of its initial elements. 
/// The current value of the iterator is always [set].
/// If iterated through to the end, the [set] ends up with all its original elements.
Iterable<Set<E>> subsets<E>(Set<E> set) sync* {
  if (set.length >= 32) {
    throw ArgumentError.value(set, "set", "must have less than 32 elements");
  }
  var list = [...set];
  var prev = 0;
  var counter = 0;
  do {
    yield set; 
    var next = ++counter ^ (counter >> 1);
    var bit = prev ^ next;  // One bit set.
    var index = bit.bitLength - 1;
    if (index >= list.length) index = 0;
    var element = list[index];
    if (next & bit == 0) {
      set.add(element);
    } else {
      set.remove(element);
    }
    prev = next;
  } while (set.length < list.length);
}