0

I have a list of lists, similar to this:

a = [ [1,2,3], [4,5,6], [7,8,9,10]]

I'd like to create all possible combinations, like this:

[(1, 4, 7), (1, 4, 8), (1, 4, 9), (1, 4, 10), (1, 5, 7), (1, 5, 8), (1, 5, 9), (1, 5, 10), (1, 6, 7), (1, 6, 8), (1, 6, 9), (1, 6, 10), (2, 4, 7), (2, 4, 8), (2, 4, 9), (2, 4, 10), (2, 5, 7), (2, 5, 8), (2, 5, 9), (2, 5, 10), (2, 6, 7), (2, 6, 8), (2, 6, 9), (2, 6, 10), (3, 4, 7), (3, 4, 8), (3, 4, 9), (3, 4, 10), (3, 5, 7), (3, 5, 8), (3, 5, 9), (3, 5, 10), (3, 6, 7), (3, 6, 8), (3, 6, 9), (3, 6, 10)]

For python, there's a library that does exactly this.
Is there a similar solution for Dart?
If not, I'd appreciate a simple code that accomplish that

user6097845
  • 1,257
  • 1
  • 15
  • 33

3 Answers3

3

One approach could be:

Iterable<List<T>> allCombinations<T>(List<List<T>> sources) sync* {
  if (sources.isEmpty || sources.any((l) => l.isEmpty)) {
    yield [];
    return;
  }
  var indices = List<int>.filled(sources.length, 0);
  var next = 0;
  while (true) {
   yield [for (var i = 0; i < indices.length; i++) sources[i][indices[i]]];
   while (true) {
      var nextIndex = indices[next] + 1;
      if (nextIndex < sources[next].length) {
        indices[next] = nextIndex;
        break;
      }
      next += 1;
      if (next == sources.length) return;
    }
    indices.fillRange(0, next, 0);
    next = 0;
  }
}

This works by effectively treating the indices as a number in variable base based on the source list lengths, then incrementing it and creating the corresponding list.

Time complexity is still (Πi(source[i].length) * source.length).

lrn
  • 64,680
  • 7
  • 105
  • 121
1

Could not find a package which does exactly what you want, but I guess your can do something like this if you want to introduce your own method:

void main() {
  print(combinations([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9, 10]
  ]));
  // ([1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 4, 10], ..., [3, 6, 9], [3, 6, 10])
}

Iterable<List<T>> combinations<T>(
    List<List<T>> lists, [
      int index = 0,
      List<T>? prefix,
    ]) sync* {
  prefix ??= <T>[];

  if (lists.length == index) {
    yield prefix.toList();
  } else {
    for (final value in lists[index]) {
      yield* combinations(lists, index + 1, prefix..add(value));
      prefix.removeLast();
    }
  }
}

More efficient solution but also more risky to use since it does require the user of combinations to take care when consuming the output and make sure not to keep any instances of the inner Iterable:

void main() {
  print(combinations([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9, 10]
  ]).map((e) => e.toList()));
  // ([1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 4, 10], ..., [3, 6, 9], [3, 6, 10])
}

Iterable<Iterable<T>> combinations<T>(
    List<List<T>> lists, [
      int index = 0,
      List<T>? prefix,
    ]) sync* {
  prefix ??= <T>[];

  if (lists.length == index) {
    yield prefix;
  } else {
    for (final value in lists[index]) {
      yield* combinations(lists, index + 1, prefix..add(value));
      prefix.removeLast();
    }
  }
}

The problem with this solution is the risk of misuse as the following example:

  final listOfCombinations = combinations([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9, 10]
  ]).toList();
  print(listOfCombinations);
  // [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]

Which should instead be:

  final listOfCombinations = combinations([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9, 10]
  ]).map((e) => e.toList()).toList();
  print(listOfCombinations);
  // [[1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 4, 10], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 5, 10], [1, 6, 7], [1, 6, 8], [1, 6, 9], [1, 6, 10], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 4, 10], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 5, 10], [2, 6, 7], [2, 6, 8], [2, 6, 9], [2, 6, 10], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 4, 10], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 5, 10], [3, 6, 7], [3, 6, 8], [3, 6, 9], [3, 6, 10]]

So, use the first suggested solution if you don't want the risk of this kind of issues. :)

julemand101
  • 28,470
  • 5
  • 52
  • 48
  • Very inefficient to create sublists on every recursive call, though :) – lrn Aug 17 '21 at 11:08
  • @lrn I agree and the solution kinda sucks so I am going to remove it again... :) - Ok... the solution got accepted before I could delete it... I kinda feel obligate to make a better solution now so I can replace this answer... :D – julemand101 Aug 17 '21 at 11:10
  • @lrn Should be better now? I am a little surprised that if I do `Iterable prefix = const Iterable.empty()` as parameter, it gets the type `Iterable` and it is not possible to do: `Iterable prefix = const Iterable.empty()`. This makes it kinda awkward when calling `followedBy` since `Never` is not a nice generic type here. So I guess the best I can do here is the workaround where `prefix` is nullable and initialize if `null`. – julemand101 Aug 17 '21 at 11:40
  • 1
    Since `T` is not constant (it depends on the invocation), it can't be used in a const expression. A const expression always evaluates to the precise same value every time it's evaluated. – lrn Aug 17 '21 at 14:04
  • 1
    Another approach is to use a list as "prefix", then do `prefix ??= []`, `yield prefix.toList();` and `prefix.add(value);yield* combinations(lists, index + 1, prefix);prefix.removeLast();`. That avoids the allocation overhead of `prefix.followedBy([value])` which is one extra list and one `Iterable.followedBy` (which will have its own iterator per nesting as well). If documented as such, you could even `yield prefix;` directly, and just require the receiver to not modify the list or reuse it after calling `moveNext` again. More dangerous, but more efficient as well. – lrn Aug 18 '21 at 09:12
  • 1
    @lrn Yeah, but if we want to indicate we don't want modifications, we could properly change the returned value of `combinations` to `Iterable>` and yield the `prefix`. But as you say, that does makes it a requirement to consume the content and don't reuse it. I think it is safest here to just yield the `prefix.toList()` but implement your suggested improvement of using `removeLast()`. – julemand101 Aug 18 '21 at 09:48
0

check out this answer. working for the problem you are searching for:

https://stackoverflow.com/a/57883482/11789758

Saud Ahmed
  • 65
  • 6