dartcartesian

Cartesian product in Dart Language


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.


Solution

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