505 votes

Obtenir le produit cartésien d'une série de listes en Python

Comment puis-je obtenir le produit cartésien (toutes les combinaisons possibles de valeurs) d'un groupe de listes ?

Entrée :

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]

Sortie souhaitée :

[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), (2, 'a', 5) ...]

39 votes

Sachez que "toutes les combinaisons possibles" n'est pas tout à fait la même chose que "produit cartésien", puisque dans les produits cartésiens, les doublons sont autorisés.

10 votes

Existe-t-il une version non dupliquée du produit cartésien ?

23 votes

@KJW Oui, set(cartesian product)

618voto

Triptych Points 70247

En Python 2.6 et plus

import itertools
for element in itertools.product(*somelists):
    print element

34 votes

Je voulais juste ajouter que le caractère '*' est nécessaire si vous utilisez la variable somelists comme indiqué dans le PO.

0 votes

Une idée de l'efficacité de la itertools.product() code ? Je suppose qu'il a été optimisé, mais je suis juste curieux (et je ne sais pas comment le calculer à partir de la page de documentation...).

1 votes

@jaska : product() génère nitems_in_a_list ** nlists éléments dans le résultat ( reduce(mul, map(len, somelists)) ). Il n'y a pas de raison de croire que le fait de céder un seul élément n'est pas O(nlists) (amorti) c'est-à-dire que la complexité temporelle est la même que pour simple emboîté for -loops par exemple, pour l'entrée de la question : nlists=3 Nombre total d'éléments dans le résultat : 3*2*2 et chaque élément a nlists articles ( 3 dans ce cas).

124voto

Jason Baker Points 56682
import itertools
>>> for i in itertools.product([1,2,3],['a','b'],[4,5]):
...         print i
...
(1, 'a', 4)
(1, 'a', 5)
(1, 'b', 4)
(1, 'b', 5)
(2, 'a', 4)
(2, 'a', 5)
(2, 'b', 4)
(2, 'b', 5)
(3, 'a', 4)
(3, 'a', 5)
(3, 'b', 4)
(3, 'b', 5)
>>>

0 votes

Les votes positifs pour cette réponse sont justifiés et encouragés, c'est la réponse la plus facile à lire et à comprendre rapidement.

44voto

J.F. Sebastian Points 102961

Pour Python 2.5 et plus :

>>> [(a, b, c) for a in [1,2,3] for b in ['a','b'] for c in [4,5]]
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), 
 (2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5), 
 (3, 'b', 4), (3, 'b', 5)]

Voici une version récursive de product() (juste une illustration) :

def product(*args):
    if not args:
        return iter(((),)) # yield tuple()
    return (items + (item,) 
            for items in product(*args[:-1]) for item in args[-1])

Exemple :

>>> list(product([1,2,3], ['a','b'], [4,5])) 
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), 
 (2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5), 
 (3, 'b', 4), (3, 'b', 5)]
>>> list(product([1,2,3]))
[(1,), (2,), (3,)]
>>> list(product([]))
[]
>>> list(product())
[()]

1 votes

La version récursive ne fonctionne pas si une partie de args sont des itérateurs.

33voto

SilentGhost Points 79627

avec itertools.product :

import itertools
result = list(itertools.product(*somelists))

7 votes

Quelle est l'utilité de * avant les somelistes ?

1 votes

@VineetKumarDoshi "produit(somelists)" est un produit cartésien entre les sous-listes de manière à ce que Python obtienne d'abord "[1, 2, 3]" comme élément et obtient ensuite un autre élément après la virgule suivante et c'est le saut de ligne, donc le premier terme du produit est ([1, 2, 3],), de même pour le second ([4, 5],) et donc "[([1, 2, 3],), ([4, 5],), ([6, 7],)]" . Si vous voulez obtenir un produit cartésien entre les éléments des tuples, vous devez indiquer à Python avec Asterisk la structure des tuples. Pour les dictionnaires, vous utilisez **. Plus d'informations sur ici .

11voto

hop Points 15423

Dans Python 2.6 et plus, vous pouvez utiliser 'itertools.product`. Dans les versions plus anciennes de Python, vous pouvez utiliser l'équivalent suivant (presque -- voir la documentation) code de la documentation :

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

Le résultat des deux est un itérateur, donc si vous avez vraiment besoin d'une liste pour un traitement ultérieur, utilisez list(result) .

0 votes

D'après la documentation, l'implémentation actuelle de itertools.product ne construit PAS de résultats intermédiaires, ce qui pourrait être coûteux. L'utilisation de cette technique pourrait rapidement devenir incontrôlable pour des listes de taille modérée.

5 votes

Je ne peux que diriger le PO vers la documentation, pas la lire pour lui.

1 votes

Le code de la documentation est destiné à démontrer ce que fait la fonction du produit, et non à servir de solution de contournement pour les versions antérieures de Python.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X