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.
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]]
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);
}
//declare type matters!
List<List<dynamic>> cards = [
[1, 2, 3],
[4, 5],
['x','y']
];
//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
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;
}
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));
}
