达特语言中的笛卡尔乘积

Question

如何在Dart语言中创建动态列表数的笛卡尔乘积？

例如，我有两个列表：X: [A, B, C]; Y: [W, X, Y, Z]

我想创建这样的列表[AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ]

虽然Python，Java已经预先实现了库，但我认为Dart语言没有。

Answer 1

使用 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]]);
}
}
}

您可以根据需要输入任意长度的字符串数组。 像这样使用：

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

输出：

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

你可以把它写成一个简单的列表：

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

(假设X和Y包含字符串，并且您想要的组合是串联，否则编写除"$x$y"以外的其他内容来组合x和y值(。

对于任意数量的列表，它会变得更加复杂。我可能更喜欢懒惰地生成组合，而不是在没有必要的情况下同时将所有列表保留在内存中。如果需要，您可以随时热切地创建它们。

也许尝试这样的事情：

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

函数求解。

//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());

也许使用Dart动态类型很傻，你可以使用类型友好的版本

我停止使用reduce函数，因为它对参数和返回值有严格的维度限制

类型友好

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

Answer 4

尝试使用此解决方案：

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