Imbrication de dictionnaires [Résolu]

[RTK45]

Bonjour à tous,

voici actuellement un exemple de ce qu'est sencé faire le script sur lequel je travail. Je dispose d'un fichier contenant 2 colonnes : des IDs et et des chiffres qui leurs sont associés.

ID **** numéros

1 **** 420
2 **** 4
3 **** 478
4 **** 4407
5 **** 13
6 **** 8701
7 **** 72237

(les étoiles servent juste de séparateur dans mon exemple).

Mon but est de récupérer toutes les combinaisons d'IDs pour lesquels la différence de leur
nombres associés ne dépasse pas un certain seuil (mettons 10 pour l'exemple). Dans cet exemple on récupérerait 2 et 5 car 13 - 4 = 9 ou 4 - 13 = -9.

J'ai donc conçu un code me permettant de récupérer dans une liste toutes les différences qui m'intéressaient, cependant je n'ai plus accès à la première colonne (correspondant aux IDs, et je n'arrive pas à remonter jusqu'à ces derniers). J'ai pensé à utiliser des dictionnaires imbriqués mais je ne trouve pas de solution efficace.

Voici mon code :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
fichier = open("mo,n_fichier.txt","rb")
 
liste = []
 
for ligne in fichier.readlines():
 
	col = ligne.split('	')    #lecture du fichier / découpage
	liste.append(col[3])   # liste contient l'ensemble des nombres
 
k = []
for c in liste:
	for i in liste:			#k contient l'ensemble des soustractions possibles
		k.append(int(i)-int((c)))
 
filtre = []
 
for t in k:
	if ((t<15) and (t> -15)):	#filtre contient l'ensemble des résultats qui satisfassent la condition
		filtre.append(t)
 
 
compteur = 0
for h in filtre:			#Elimination des 0 correspondant à la soustraction d'un ID par lui même
	if h!=0:
		compteur = compteur + 1 
print compteur				 #comptage des données qui satisfassent ma condition...

Au final j'obtiens donc une liste contenant les valeurs qui m’intéressent, mais j'aimerai pouvoir remonter aux IDs qui ont été utilisé pour réaliser cette soustraction.

Est'il possible d'y parvenir en utilisant les listes ?

J'avais pensé à l'utilisation de dictionnaires imbriqués mais je me suis toujours limité à des cas "simples" d'utilisation de dictionnaires, je suis donc un peu perplexe quant à l'utilisation de cette méthode, j'avais pensé à quelque chose comme ça :

Code :

di = {ID:{'soustraction1'="ID1",'soustraction2'=ID1}}...

Mercià vous, si ce n'est pas clair n'hésitez pas à me poser des questions

[VinsS]

Salut,

Je trouve ceci bizarre:

Code :

1
2
 
liste.append(col[3])

je suppose que c'est col[1]


quoiqu'il en soit, tu peux directement conserver tes index lors de la soustraction.

Dans un set pour éviter les inverses:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
# -*- coding: utf-8 -*-
 
with open("values.txt", "r") as inf:
    d = {}
    for line in inf.readlines():
        k, v = line.split('    ')
        d[k] = int(v)
 
result = set()
for k1 in d.keys():
    for k2 in d.keys():
        if d[k1] - d[k2] in range(1, 10):
            result.add((k1, k2))
        elif d[k1] - d[k2] in range(-1, -10):
            result.add((k2, k1))
 
print result

Testé à la va-vite.

[Sve@r]

Envoyé par RTK45

Voici mon code :

Code :

...

Salut

Voici mon fichier test

Code :

1
2
3
4
5
6
7
8
9
1:420
2:4
3:478
4:4407
5:13
6:8701
7:72237 
8:12
9:7

Si j'ai bien compris ton problème, alors
- l'identifiant 2 est associé avec 5, 8 et 9
- l'identifiant 5 est associé avec 2, 8 et 9
- l'identifiant 8 est associé avec 2, 5 et 9
- l'identifiant 9 est associé avec 2, 5 et 8

Donc voici mon code

Code python :

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
fp=open(fichier, "r")
map=[(int(x), int(y)) for (x, y) in [lig.replace("\n", "").split(":") for lig in fp]]
#print map
fp.close()
 
result={}
for couple in map:
	result[couple[0]]=[x[0] for x in map if x[0] != couple[0] and abs(couple[1] - x[1]) < 10]
 
print result

Et ce que ça donne

Code :

{1: [], 2: [5, 8, 9], 3: [], 4: [], 5: [2, 8, 9], 6: [], 7: [], 8: [2, 5, 9], 9: [2, 5, 8]}

[tyrtamos]

Bonjour,

Si j'ai bien compris le problème, je crois avoir trouvé une solution.

Considérons que nous avons déjà extrait la simple liste des nombres terminaux dans l'ordre, et que nous avons défini le seuil:

Code :

1
2
L = [420, 4, 478, 4407, 13, 8701, 72237]
seuil = 10

Nous cherchons la "combinaison" des nombres de L pris 2 à 2, au sens de l'analyse combinatoire. Et ça, c'est facile, puisque la fonction "combinations" du module itertools fait ça très bien:

Code :

1
2
3
4
from itertools import combinations
LC = [[x, y]   for x, y in combinations(L,2)]
print LC
[[420, 4], [420, 478], [420, 4407], [420, 13], [420, 8701], [420, 72237], [4, 478], [4, 4407], [4, 13], ... ,[13, 72237], [8701, 72237]]

On peut ensuite tester lequel répond à la condition: abs(x-y)<seuil. On voit ici que c'est la liste [4,13] situé à l'indice 8 qui gagnera.

Et la "remontée" aux indices initiaux est facile aussi. Si on crée la même combinaison des nombres de la liste [0,1,2,3,4,5,6] pris 2 à 2, on trouvera:

Code :

1
2
3
4
I = [0,1,2,3,4,5,6]
IC = [[i1, i2] for i1,i2 in combinations(I,2)]
print IC
[[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [1, 2], [1, 3], [1, 4], [1, 5], ...,  [4, 6], [5, 6]]

On voit ici que la liste située à l'indice 8 est [1,4] et que ce sont les indices initiaux des 2 valeurs [4,13] trouvées précédemment au même indice 8:
=> le 4 vient donc de l'indice 1 de la liste initiale et
=> le 13 de l'indice 4 de la liste initiale

Voilà la récap du code:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
from itertools import combinations
 
L = [420, 4, 478, 4407, 13, 8701, 72237]
seuil = 10
 
I = [i for i in range(0,len(L))] # [0,1,2,3,4,5,6]
 
LC = [[x, y]   for x, y in combinations(L,2)]
IC = [[i1, i2] for i1,i2 in combinations(I,2)]
for i, (x,y) in enumerate(LC):
    if abs(x-y)<seuil:
        print "On trouve à l'indice %d des combinaisons: %d (indice initial %d) et %d (indice initial %d)" % (i, x, IC[i][0], y, IC[i][1])

Ce qui affiche:

On trouve à l'indice 8 des combinaisons: 4 (indice initial 1) et 13 (indice initial 4)

[RTK45]

Merci à tous pour vos réponses et pour le temps que vous avez consacré à mon problème. Je vais de ce pas étudier vos solutions

Salut,

Je trouve ceci bizarre:
Code :Sélectionner tout - Visualiser dans une fenêtre à part
1
2

liste.append(col[3])

Oui autant pour moi en fait le code que j'ai montré était celui appliqué à mon cas concret et non à l'exemple donné ici.

Malgrès mes piètres explications vous avez cernés le soucis, j'aurai dû matérialiser le problème autrement, on peut imaginer que les IDs correspondent à des numéros de coureurs et que les nombres représentent leurs positions kilométriques, je veux donc récupérer les couples de coureurs qui sont séparés par une distance X.

[RTK45]

Merci encore pour vos codes ils m'ont beaucoup aidé et j'ai appris des choses (je ne connaissais pas la fonction valeur absolue (shame on me), j'ai découvert le module "combinations" qui est en effet très efficace et simple d'utilisation, il a juste fallut que je cast la soustraction et que je remplace le type des outputs en %s.

Merci encore,

Bonne journée

[dividee]

Pourquoi pas un petit algo en O(n*log(n)) tant qu'à faire ?
(du moins tant que le nombre de couples sélectionnés reste petit par rapport au nombre de couples possibles):

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
with open("...") as f:
    entries = [(int(y),int(x)) for (x,y) in (line.strip().split(":") for line in f)] # adapté du code de Sve@r
entries.sort()   # c'est de là que vient le O(n*log(n))
couples = []
imin = 0
imax = 1
seuil = 10
while imax < len(entries):
    if entries[imax][0] - entries[imin][0] < seuil:
        for i in range(imin, imax):
            couples.append((entries[i][1],entries[imax][1]))
        imax += 1
    else:
        imin += 1
        if imin == imax:
            imax += 1
 
print couples