Trouver toutes les associations possibles entre les valeurs de deux listes

**AdrienVH** · 04/05/2017, 11h45

Bonjour à tous,

Je possède deux listes (représentant des origines et destinations) de même dimension :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
a = ["A","B","C"]
b = ["D","E","F"]

Et j'aimerais lister toutes les combinaisons possibles deux à deux, telles que :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

c = [["AD","BE","CF"], ["AD","BF","CE"], ["AE","BD","CF"], ["AE","BF","CD"], ["AF","BD","CF"], ["AF","BE","CE"]]

Autre exemple (plus simple, pour comprendre la logique ciblée) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
a = ["A","B"]
b = ["C","D"]

Ce qui donnerait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

c = [["AC","BD"], ["AD","BC"]]

Le nombre de combinaisons possibles pour des listes de 4 dimensions est 4x3x2x1 (24), de 3 dimensions est 3x2x1 (6), etc.

J'ai fait plusieurs tests, mais je n'arrive pas à construire l'algorithme qui fonctionne quelque soit la dimension de mes deux listes et sans créer de redondance (["AC","BD"] et ["BD","AC"]).

Je vous remercie par avance pour votre aide !

Adrien

**afranck64** · 04/05/2017, 12h24

En supposant que les combinaisons soient déjà disponibles,
tu peux traiter la liste de toutes les combinaisons possibles comme une matrice, et le résultat que tu désires serait juste les colonnes de ta matrice.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
combinaisons = ['AD', 'AE', 'AF', 'BD', 'BE', 'BF', 'CD', 'CE', 'CF']
 
SIZE = 3
 
print (combinaisons)
 
res = []
for i in range(SIZE):
	group = []
	for j in range(SIZE):
		group.append(combinaisons[j*SIZE+i])
	res.append(group)
 
print (res)
 
### output
['AD', 'AE', 'AF', 'BD', 'BE', 'BF', 'CD', 'CE', 'CF']
[['AD', 'BD', 'CD'], ['AE', 'BE', 'CE'], ['AF', 'BF', 'CF']]

**AdrienVH** · 04/05/2017, 13h21

Bonjour et merci pour ta réponse.

Malheureusement, je crois que mon problème n'a pas été bien exposé car ta réponse ne correspond pas à mon besoin.

Je dois associer une origine (A, B, C) à une destination (D, E, F) et lister toutes les combinaisons d'associations (6 pour deux listes de taille 3) :

Combinaison n°1 : A relié à D, B relié à E et C relié à F
Combinaison n°2 : A relié à D, B relié à F et C relié à E
Combinaison n°3 : A relié à E, B relié à D et C relié à F
Combinaison n°4 : A relié à E, B relié à F et C relié à D
Combinaison n°5 : A relié à F, B relié à D et C relié à F
Combinaison n°6 : A relié à F, B relié à E et C relié à E

Pour info, connaître toutes les associations possibles n'est pas compliqué du tout :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
origines = ["A", "B", "C"]
destinations = ["D", "E", "F"]
associations = []
for origine in origines:
    for destination in destinations:
        associations.append([origine, destination])
print(associations)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[['A', 'D'], ['A', 'E'], ['A', 'F'], ['B', 'D'], ['B', 'E'], ['B', 'F'], ['C', 'D'], ['C', 'E'], ['C', 'F']]

Dans notre cas, elles vont servir plusieurs fois (l'association B-F se retrouve par exemple dans les combinaisons n°2 et n°4).

**marco056** · 04/05/2017, 13h24

Pour obtenir les combinaisons précédentes, c'est assez facile :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
a = ["A","B","C"]
b = ["D","E","F"]
 
c=[]
for i in range(len(a)):
    for j in range(len(b)):
        c.append(a[i]+b[j])
 
print(c)

**bistouille** · 04/05/2017, 19h22

J'ai regardé dans itertools, j'ai pas trouvé de fonction pouvant faire cela, mais product peut servir.

Je ne sais pas si c'est exactement ce que tu voulais, mais d'parès ce que j'ai compris oui.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import itertools
import re
 
def association(liste1, liste2, combinaison) :
    resultat = set()
    for n in itertools.product(liste1, liste2, repeat=combinaison) :
        setn = set(n)
        if len(setn) == len(n) :
            liste = [v for v in re.split('(\w{2})', ''.join(n)) if v]
            resultat.add(tuple(sorted(liste)))
    return sorted(resultat)
 
a = ["A","B"]
b = ["C", "D"]
 
# [('AC', 'BD'), ('AD', 'BC')]
print(association(a, b, 2))
 
 
a = ["A","B","C"]
b = ["D","E","F"]
 
# [('AD', 'BE', 'CF'), ('AD', 'BF', 'CE'), ('AE', 'BD', 'CF'), ('AE', 'BF', 'CD'), ('AF', 'BD', 'CE'), ('AF', 'BE', 'CD')]
print(association(a, b, 3))

**BufferBob** · 05/05/2017, 02h07

salut,

en fait il se peut qu'on puisse décortiquer le problème différemment, finalement l'origine dont tu parles ne bouge pas, c'est toujours la même ['A', 'B', 'C'], et tu veux associer cette origine à chacune des permutations de l'ensemble ['D', 'E', 'F'] :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
>>> list(itertools.permutations(['D', 'E', 'F']))
[('D', 'E', 'F'), ('D', 'F', 'E'), ('E', 'D', 'F'), ('E', 'F', 'D'), ('F', 'D', 'E'), ('F', 'E', 'D')]

il restera simplement pour chaque triplet à l'associer avec l'origine, à coups de zip() par exemple et moyennant une fonction pour mettre le tout en forme

à la dégueu et pour montrer que ça fonctionne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
>>> f=lambda x: [''.join(x[i]) for i in range(len(x))]
>>> [f(zip('ABC', j)) for j in [''.join(i) for i in list(itertools.permutations('DEF'))]]
[['AD', 'BE', 'CF'], ['AD', 'BF', 'CE'], ['AE', 'BD', 'CF'], ['AE', 'BF', 'CD'], ['AF', 'BD', 'CE'], ['AF', 'BE', 'CD']]