4
votes

Produit cartésien en langage Dart

Comment puis-je créer un produit cartésien d'un nombre dynamique de listes en langage Dart?

Par exemple, j'ai deux listes: X: [A, B, C]; Y: [W, X, Y, Z]

Je souhaite créer des listes comme celle-ci [AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ]

Bien que Python, Java aient des bibliothèques pré-implémentées, je pense qu'il n'y en a pas pour le langage Dart.


0 commentaires

4 Réponses :


0
votes

Essayez avec cette 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));
}


1 commentaires

Je pense que c'est spécifiquement pour deux listes et non pour un nombre inconnu de listes.



3
votes

Vous pouvez écrire ceci sous forme de liste simple:

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

(en supposant que X et Y contiennent des chaînes et que la combinaison souhaitée est la concaténation, sinon écrivez autre chose que "$x$y" pour combiner les valeurs x et y ).

Pour un nombre arbitraire de listes, cela devient plus compliqué. Je préférerais probablement générer les combinaisons paresseusement, au lieu d'avoir à garder toutes les listes en mémoire en même temps si ce n'est pas nécessaire. Vous pouvez toujours les créer avec empressement si nécessaire.

Essayez peut-être quelque chose comme:

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


3 commentaires

Je pense que c'est spécifiquement pour deux listes et non pour un nombre inconnu de listes.


Bon point. Le "nombre dynamique de listes" le rend plus compliqué.


Oui monsieur. C'est le principal problème auquel je suis confronté.



3
votes

Testé avec Dart 2.5.0:

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

Vous pouvez saisir n'importe quelle longueur de tableaux de chaînes comme vous le souhaitez. Utilisez comme ceci:

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

Production:

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


2 commentaires

Un code fantastique. Comment avez-vous appris celui-ci? Puis-je obtenir une référence?


J'ai appris de la mise en œuvre d'autres langues. Il existe de nombreux exemples et réponses de Google. L'idée de base est la même, essayez d'utiliser des appels récursifs pour le résoudre.



0
votes

Résolution fonctionnelle.
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;
}

produit cartésien

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

Peut-être que l'utilisation du type dynamique Dart est idiot, vous pouvez utiliser la version conviviale du type

J'ai arrêté d'utiliser la fonction de réduction en raison de sa dimension stricte limitant les paramètres et renvoyant des valeurs

Type convivial

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

1 commentaires

PS. Les codes Dart styles dynamiques lang, mais il est statique et omet la vérification de type, ce qui me fait vraiment me sentir bizarre.