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.

Felixfeliza

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]]

Actinopod

A fantastic code. How did you learn this one? Can I get any reference? – Felixfeliza

I learnt from the implementation of other languages. There are a lot of examples and answers from Google. The basic idea is the same, try to use recursive calls to solve it. – Actinopod

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);
}

Aftereffect

I think this is specifically for two lists not for unknown number of lists. – Felixfeliza

Good point. The "dynamic number of lists" makes it mroe complicated. – Aftereffect

Yes sir. That is the main problem I am facing. – Felixfeliza

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

Maine

PS. Dart codes styles dynamic lang,but it is static and casually omits type check ,which really make me feel weird. – Maine

Answer 4

Try with this solution:

void main() {
  List<String> a = ['A','B','C'];
  List<String> b = ['X','Y','Z'];
  List<String> c = a.map((ai) => b.map((bi) => ai+bi).toList()).expand((i) => i).toList();
  c.forEach((ci) => print(ci));
}

Homocercal

I think this is specifically for two lists not for unknown number of lists. – Felixfeliza