Cette question demande comment calculer le produit cartésien d'un nombre donné de vecteurs . Étant donné que le nombre de vecteurs est connu à l'avance et plutôt petit, la solution est facilement obtenue avec des boucles imbriquées.
Supposons maintenant que vous recevez, dans votre langue de choix, un vecteur de vecteurs (ou liste des listes, ou Ensemble d'ensembles, etc.): Si on m'a demandé de calculer son produit cartésien, c'est Je procéderais à la récursion. Par exemple, dans le python rapide et sale, est un moyen facile de le calculer itératif ? (Remarque: la réponse n'a pas besoin d'être en Python et de toute façon je suis conscient que, dans Python Itertools, le travail est meilleur, comme dans Cette question .)
4 Réponses :
1) Créez une liste d'index dans les listes correspondantes, initialisées à 0, c'est-à-dire: 2) donnez l'élément approprié de chaque liste (dans ce cas le premier). 3) augmente le dernier index d'une. p> 4) Si le dernier index est égal à la longueur de la dernière liste, réinitialisez-la à zéro et en portant une. Répétez cette opération jusqu'à ce qu'il n'y ait pas de transport. P> 5) Retournez à l'étape 2 jusqu'à ce que les index enveloppent sur [0,0,0,0,0,0] p> C'est similaire à la manière dont les travaux de comptage, à l'exception de la base de chaque chiffre peuvent être différents. p> Voici une implémentation de l'algorithme ci-dessus en Python: P>
def cartesian_product(aListOfList):
i = 0
while True:
result = []
j = i
for l in aListOfList:
result.append(l[j % len(l)])
j /= len(l)
if j > 0: return
yield result
i += 1
Ouais. Plutôt facile en effet. Merci.
Je pense que votre code est en fait légèrement plus inefficace que votre algorithme ..; p
Oui ... J'ai une autre version qui correspond étroitement à l'algorithme, mais dans la pensée, c'était assez déroutant! Peut-être que je peux le poster quand même ...
@Larry: J'ai posté ma première version maintenant! Peut-être que cela pourrait être écrit plus soigneusement, mais ça marche ...
=) Juste en disant, parce que lorsque je soumets ma réponse et que je vous ai vu, et le vôtre est clairement plus efficace!
La solution à l'aide de l'incrémente le premier élément du premier élément cependant.
Itéréter de 0 à Il y a aussi des moyens triviaux d'écrire cela afin de l'écrire ne pas avoir à faire le même travail deux fois. \ pi a_i_length pour tous i .
Vous devez simplement gérer votre pile manuellement. Fondamentalement, faites quelle récursion fait par vous-même. Puisque la récursivité met des données sur chaque appel récursif sur une pile, vous faites simplement la même chose: EDIT : Eh bien, trop tard, je suppose. Ceci est fondamentalement la même chose que le comptage, juste une autre façon de le regarder.
Depuis que vous avez demandé une solution de langue-agnostique, voici un à bash, mais pouvons-nous l'appeler itératif, récursif, qu'est-ce que c'est? C'est juste la notation: peut-être assez intéressant.