Opération sur chaque paire d'éléments dans une liste

Question

En utilisant Python, j'aimerais comparer toutes les paires possibles dans une liste.

Supposons que j'ai

my_list = [1,2,3,4]

J'aimerais effectuer une opération (appelons-la foo) sur chaque combinaison de deux éléments de la liste.

Le résultat final devrait être le même que

foo(1,1)
foo(1,2)
...
foo(4,3)
foo(4,4)

Ma première idée était d'itérer deux fois dans la liste manuellement, mais cela ne semble pas très pythonique.

Answer 1

Vérifiez product() dans le itertools module. Il fait exactement ce que vous décrivez.

import itertools

my_list = [1,2,3,4]
for pair in itertools.product(my_list, repeat=2):
    foo(*pair)

Ceci est équivalent à :

my_list = [1,2,3,4]
for x in my_list:
    for y in my_list:
        foo(x, y)

Editar: Il existe également deux fonctions très similaires, permutations() y combinations() . Pour illustrer comment ils diffèrent :

product() génère toutes les paires d'éléments possibles, y compris tous les doublons :

1,1  1,2  1,3  1,4
2,1  2,2  2,3  2,4
3,1  3,2  3,3  3,4
4,1  4,2  4,3  4,4

permutations() génère tous les ordonnancements uniques de chaque paire unique d'éléments, éliminant ainsi les x,x les doublons :

 .   1,2  1,3  1,4
2,1   .   2,3  2,4
3,1  3,2   .   3,4
4,1  4,2  4,3   .

Enfin, combinations() ne génère que chaque paire unique d'éléments, dans l'ordre lexicographique :

 .   1,2  1,3  1,4
 .    .   2,3  2,4
 .    .    .   3,4
 .    .    .    .

Ces trois fonctions ont été introduites dans Python 2.6.

Answer 2

J'ai eu un problème similaire et j'ai trouvé la solution aquí . Il fonctionne sans avoir à importer un quelconque module.

Supposons une liste comme :

people = ["Lisa","Pam","Phil","John"]

Une solution simplifiée en une ligne ressemblerait à ceci.

Toutes les paires possibles y compris les doublons :

result = [foo(p1, p2) for p1 in people for p2 in people]

Toutes les paires possibles, à l'exclusion des doublons :

result = [foo(p1, p2) for p1 in people for p2 in people if p1 != p2]

Paires uniques où l'ordre n'a pas d'importance :

result = [foo(people[p1], people[p2]) for p1 in range(len(people)) for p2 in range(p1+1,len(people))]

---

Dans le cas où vous ne voulez pas opérer mais juste obtenir les paires, supprimez la fonction foo et l'utilisation d'un simple tuple serait suffisante.

Toutes les paires possibles y compris les doublons :

list_of_pairs = [(p1, p2) for p1 in people for p2 in people]

Résultat :

('Lisa', 'Lisa')
('Lisa', 'Pam')
('Lisa', 'Phil')
('Lisa', 'John')
('Pam', 'Lisa')
('Pam', 'Pam')
('Pam', 'Phil')
('Pam', 'John')
('Phil', 'Lisa')
('Phil', 'Pam')
('Phil', 'Phil')
('Phil', 'John')
('John', 'Lisa')
('John', 'Pam')
('John', 'Phil')
('John', 'John')

Toutes les paires possibles, à l'exclusion des doublons :

list_of_pairs = [(p1, p2) for p1 in people for p2 in people if p1 != p2]

Résultat :

('Lisa', 'Pam')
('Lisa', 'Phil')
('Lisa', 'John')
('Pam', 'Lisa')
('Pam', 'Phil')
('Pam', 'John')
('Phil', 'Lisa')
('Phil', 'Pam')
('Phil', 'John')
('John', 'Lisa')
('John', 'Pam')
('John', 'Phil')

Paires uniques où l'ordre n'a pas d'importance :

list_of_pairs = [(people[p1], people[p2]) for p1 in range(len(people)) for p2 in range(p1+1,len(people))]

Résultat :

('Lisa', 'Pam')
('Lisa', 'Phil')
('Lisa', 'John')
('Pam', 'Phil')
('Pam', 'John')
('Phil', 'John')

Edit : Après avoir retravaillé pour simplifier cette solution, j'ai réalisé que c'est la même approche que celle d'Adam Rosenfield. J'espère que l'explication plus large aidera certains à mieux la comprendre.

Answer 3

Si vous n'appelez qu'une fonction, vous ne pouvez pas vraiment faire mieux :

for i in my_list:
    for j in my_list:
        foo(i, j)

Si vous voulez rassembler une liste des résultats de l'appel de la fonction, vous pouvez le faire :

[foo(i, j) for i in my_list for j in my_list]

qui vous renverra une liste du résultat de l'application de foo(i, j) à chaque paire possible (i, j) .

Answer 4

Réponse de Ben Bank fonctionne bien si vous voulez que les combinaisons soient ordonnées lexicographiquement. Cependant, si vous souhaitez que les combinaisons soient ordonnées de manière aléatoire, voici une solution :

import random
from math import comb

def cgen(i,n,k):
    """
    returns the i-th combination of k numbers chosen from 0,1,...,n-1

    forked from: https://math.stackexchange.com/a/1227692
    changed from 1-indexed to 0-indexed.
    """
    # 1-index
    i += 1

    c = []
    r = i+0
    j = 0
    for s in range(1,k+1):
        cs = j+1
        while r-comb(n-cs,k-s)>0:
            r -= comb(n-cs,k-s)
            cs += 1
        c.append(cs-1)
        j = cs
    return c

def generate_random_combinations(n, k, shuffle=random.shuffle):
    """
    Generate combinations in random order of k numbers chosen from 0,1,...,n-1.

    :param shuffle: Function to in-place shuffle the indices of the combinations. Use for seeding.
    """
    total_combinations = comb(n, k)
    combination_indices = list(range(total_combinations))
    shuffle(combination_indices)

    for i in combination_indices:
        yield cgen(i, n, k)

Exemple d'utilisation

Para N=100 y k=4 :

gen_combos = generate_random_combinations(100, 4)

for i in range(3):
    print(next(gen_combos))

résulte en :

[4, 9, 55, 79]
[11, 49, 58, 64]
[75, 82, 83, 91]

Cas d'utilisation

Pour mon cas d'utilisation, j'implémente un algorithme qui recherche une seule (ou quelques) combinaison(s) et s'arrête lorsqu'il trouve une combinaison valide. En moyenne, il parcourt un très petit sous-ensemble de toutes les combinaisons possibles, donc il n'y a pas besoin de construire toutes les combinaisons possibles à l'avance puis de les mélanger (la taille de la population est trop grande pour faire tenir toutes les combinaisons en mémoire, de toute façon).

Le caractère aléatoire est crucial pour trouver rapidement une solution, car l'ordre lexicographique fait qu'une seule valeur de la population est incluse dans toutes les combinaisons jusqu'à ce qu'elle soit épuisée. Par exemple, si nous avons n=100 y k=4 alors les résultats seront les suivants :

indice

combinaison

0

(0, 1, 2, 3)

1

(0, 1, 2, 4)

2

(0, 1, 2, 5)

...

156848

(0, 97, 98, 99)

156849

(1, 2, 3, 4)

Si 0 ne fait pas partie d'une solution valide, alors nous aurons cherché 156849 combinaisons sans raison. Le fait de rendre l'ordre aléatoire permet d'atténuer ce problème (voir l'exemple ci-dessus).

Answer 5

my_list = [1,2,3,4]

pairs=[[x,y] for x in my_list for y in my_list]
print (pairs)