Cartesian product in Dart Language

Question

How can I create Cartesian Product of dynamic number of lists in Dart Language ?

For example I have two lists: X: [A, B, C]; Y: [W, X, Y, Z]

I want to create lists like this [AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ]

Although Python, Java have pre implemented libraries, there is none for Dart language I think.

Answer 1

Tested with Dart 2.5.0:

class PermutationAlgorithmStrings {
  final List<List<String>> elements;

  PermutationAlgorithmStrings(this.elements);

  List<List<String>> permutations() {
    List<List<String>> perms = [];
    generatePermutations(elements, perms, 0, []);
    return perms;
  }

  void generatePermutations(List<List<String>> lists, List<List<String>> result, int depth, List<String> current) {
    if (depth == lists.length) {
      result.add(current);
      return;
    }

    for (int i = 0; i < lists[depth].length; i++) {
      generatePermutations(lists, result, depth + 1, [...current, lists[depth][i]]);
    }
  }
}

You can input any length of string arrays as you like. Use like this:

  PermutationAlgorithmStrings algo = PermutationAlgorithmStrings([
                      ["A", "B", "C"],
                      ["W", "X", "Y", "Z"],
                      ["M", "N"]
                    ]);

Output:

output: [[A, W, M], [A, W, N], [A, X, M], [A, X, N], [A, Y, M], [A, Y, N], [A, Z, M], [A, Z, N], [B, W, M], [B, W, N], [B, X, M], [B, X, N], [B, Y, M], [B, Y, N], [B, Z, M], [B, Z, N], [C, W, M], [C, W, N], [C, X, M], [C, X, N], [C, Y, M], [C, Y, N], [C, Z, M], [C, Z, N]]

Answer 2

You can write this as a simple list:

var product = [for (var x in X) for (var y in Y) "$x$y"];

(assuming X and Y contain strings and the combination you want is concatenation, otherwise write something else than "$x$y" to combine the x and y values).

For an arbitrary number of lists, it gets more complicated. I'd probably prefer to generate the combinations lazily, instead of having to keep all the lists in memory at the same time if it isn't necessary. You can always create them eagerly if needed.

Maybe try something like:

Iterable<List<T>> cartesian<T>(List<List<T>> inputs) sync* {
  if (inputs.isEmpty) { 
    yield List<T>(0);
    return;
  }
  var indices = List<int>.filled(inputs.length, 0);
  int cursor = inputs.length - 1;
  outer: do {
    yield [for (int i = 0; i < indices.length; i++) inputs[i][indices[i]]];
    do {
      int next = indices[cursor] += 1;
      if (next < inputs[cursor].length) {
        cursor = inputs.length - 1;
        break;
      }
      indices[cursor] = 0;
      cursor--;
      if (cursor < 0) break outer;
    } while (true);
  } while (true);
}

Answer 3

Functional solve.

//declare type matters!
List<List<dynamic>> cards = [
    [1, 2, 3],
    [4, 5],
    ['x','y']
  ];

cartesian product

//or List flatten(List iterable) => iterable.expand((e) => e is List ? flatten(e) : [e]).toList(); // toList() cannot omit
Iterable flatten(Iterable iterable) => iterable.expand((e) => e is Iterable ? flatten(e) : [e]); 

//cannot omit  paramenter type 
List<List<dynamic>> cartesian(List<List<dynamic>> xs) =>
    xs.reduce((List<dynamic> acc_x, List<dynamic> x) =>  // type cannot be omit
        acc_x.expand((i) => x.map((j) => flatten([i, j]).toList())).toList());

Maybe use Dart dynamic type is silly, you can use type friendly version

I quit using reduce function because of its strict dimension limiting on parameters as well as returning values

Type friendly

List<List<T>> cartesian<T>(List<List<T>> list) {
  var head = list[0];
  var tail = list.skip(1).toList();
  List<List<T>> remainder = tail.length > 0 ? cartesian([...tail]) : [[]];
  List<List<T>> rt = [];
  for (var h in head) {
    for (var r in remainder)
      rt.add([h, ...r]);
  }    
  return rt;
}