liste de liste

Version imprimable

Voir 40 message(s) de cette discussion en une page

liste de liste

Bonjour,
je suis débutant en python et j'essaie de retourner la taille d'une liste de liste. ça marche si je le fais simplement mais je voudrais l'utiliser dans une boucle et ça ne marche plus.

Code:

1
2
3
4
5
6
7
8
9
10
def arete_inter(c):
 
    poids = 0
    for i in c[0]:
        taille = len(Adj_liste[i])
        for j in range(taille):
            if j in c[1]:
                poids += 1
##    poids = sum( 1 for i in c[0] for j in range(len(Adj_liste[i])) if j in c[1] )
    return poids

ici, c est une liste de deux listes
Adj_liste est une liste de liste

Code:

1
2
c =  ([0, 2, 3, 5, 6, 7, 8, 11, 13, 17], [1, 4, 9, 10, 12, 14, 15, 16, 18, 19])
Adj_liste =  [[1, 2, 5, 6, 8, 10, 14, 16, 17, 18], [2, 3, 6, 7, 9, 10, 12, 13, 14, 16, 17, 18], [3, 4, 5, 6, 7, 9, 14, 16, 17, 18], [4, 5, 11, 15, 16], [5, 6, 9, 16, 18], [8, 10, 14, 15, 16, 17, 18], [7, 9, 11, 12, 13, 15, 16, 17], [8, 10, 12, 13, 14, 16, 18], [9, 10, 12, 13, 14, 16, 18], [10, 14, 17, 18], [11, 13, 14, 15, 17, 18], [12, 15, 17, 18], [14, 16, 17, 18], [15, 16, 17, 18], [], [], [18], [18], []]

Merci de votre aide.

02/04/2010, 04h52
miawaw

La boucle ainsi que la ligne en commentaire donnent toutes les deux 18.
C'est pas ça normalement ?

Citation:

Envoyé par hyuga33

j'essaie de retourner la taille d'une liste de liste

Code:

1
2
3
4
5
6
7
8
9
10
11
 
def arete_inter(c):
 
    poids = 0
    for i in c[0]:
        taille = len(Adj_liste[i])
        for j in range(taille):
            if j in c[1]:
                poids += 1
##    poids = sum( 1 for i in c[0] for j in range(len(Adj_liste[i])) if j in c[1] )
    return poids

Code:

1
2
c =  ([0, 2, 3, 5, 6, 7, 8, 11, 13, 17], [1, 4, 9, 10, 12, 14, 15, 16, 18, 19])
Adj_liste =  [[1, 2, 5, 6, 8, 10, 14, 16, 17, 18], [2, 3, 6, 7, 9, 10, 12, 13, 14, 16, 17, 18], [3, 4, 5, 6, 7, 9, 14, 16, 17, 18], [4, 5, 11, 15, 16], [5, 6, 9, 16, 18], [8, 10, 14, 15, 16, 17, 18], [7, 9, 11, 12, 13, 15, 16, 17], [8, 10, 12, 13, 14, 16, 18], [9, 10, 12, 13, 14, 16, 18], [10, 14, 17, 18], [11, 13, 14, 15, 17, 18], [12, 15, 17, 18], [14, 16, 17, 18], [15, 16, 17, 18], [], [], [18], [18], []]

Merci de votre aide.

ce que je comprends de ton code c'est qu'il cumule le nombre d'elements de chaque sous-liste de Adj_liste qui apparaissent dans c[1] ... donc je ne vois pas le rapport avec la question.

sinon pour deplier une liste de listes à 1 niveau tu peux faire :

Code:

sum(liste,[])

02/04/2010, 12h23
hyuga33

En fait, je veux incrémenter poids à chaque fois que:
i un element de c[0] me donne l'emplacement de ma première liste soit L.
si j un element de c[2] est dans ma liste L de Adj_liste.

La ligne en commentaire était une autre implémentation de mon code donc oui c'est normal que ça renvoie la même chose.

Citation:

Envoyé par josmiley

ce que je comprends de ton code c'est qu'il cumule le nombre d'elements de chaque sous-liste de Adj_liste qui apparaissent dans c[1]

je pense que ce que huga33 fait est différent
Citation:
Envoyé par hyuga33
Code:

1 2 3 4 5 6 7 8 9 10 def arete_inter(c): poids = 0 for i in c[0]: taille = len(Adj_liste[i]) for j in range(taille): if j in c[1]: poids += 1 ## poids = sum( 1 for i in c[0] for j in range(len(Adj_liste[i])) if j in c[1] ) return poids
Ce que je comprend, c'est que
1 ° on prend les listes de Adj_liste qui on pour indices les elements de c[0]
2 ° on regarde la taille de chaque liste
3 ° pour chaque taille de chaque liste, on regarde le nombre d'éléments de c[1] qui sont plus petits que cette taille. (c'est un peu brouillon ça)
4 ° on somme tout (d'où le poids +=1 intempestif)
C'est ça hyuga33 ?

désolé, j'ai du mal à expliquer.
Code:

1 2 c = ([0, 2, 3, 5, 6, 7, 8, 11, 13, 17], [1, 4, 9, 10, 12, 14, 15, 16, 18, 19]) Adj_liste = [[1, 2, 5, 6, 8, 10, 14, 16, 17, 18], [2, 3, 6, 7, 9, 10, 12, 13, 14, 16, 17, 18], [3, 4, 5, 6, 7, 9, 14, 16, 17, 18], [4, 5, 11, 15, 16], [5, 6, 9, 16, 18], [8, 10, 14, 15, 16, 17, 18], [7, 9, 11, 12, 13, 15, 16, 17], [8, 10, 12, 13, 14, 16, 18], [9, 10, 12, 13, 14, 16, 18], [10, 14, 17, 18], [11, 13, 14, 15, 17, 18], [12, 15, 17, 18], [14, 16, 17, 18], [15, 16, 17, 18], [], [], [18], [18], []]
en fait Adj_liste est une liste d'ajacence qui pour chaque "sous liste" indique les voisins du sommet.
par exemple, si je considére le sommet 3, c'est voisin sont:

Code:

[3, 4, 5, 6, 7, 9, 14, 16, 17, 18]

Ici, 3 est un élément de c[0], maintenant je parcours la liste ci-dessus et dès qu'un élément de c[1] est dans cette liste alors j'incrémente poids.
Dans ce cas, poids = 5
Je fais ça sur tout les éléments de c[0]

Voici mon code en entier.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
 
# -*- coding: cp1252 -*-
# ==============================================================================
# METHODE RECUIT SIMULE
# ==============================================================================
"""ALGORITHME RECUIT SIMULE"""
__author__  = ""
__version__ = "1.0"
__date__    = " Avril 2009 "
__usage__   = " Mini-Projet."
# ------------------------------------------------------------------------------
from random import randrange, sample, choice, random, randint
from math import log, exp
import time
# ------------------------------------------------------------------------------
def complementaire():
    """renvoie la classe complementaire de c1: c2"""
    c1 = (sample(xrange(nb_sommet),int(nb_sommet/2)))
    c2 = [ i for i in xrange(nb_sommet) if not (i in c1) ]
    c1.sort()
    c2.sort()
    return c1, c2   
# ------------------------------------------------------------------------------
def configinit():
    """construit la classe initiale c1"""
    return (sample(xrange(nb_sommet),int(nb_sommet/2)))
# ------------------------------------------------------------------------------
def arete_inter(c):
 
    poids = 0
    for i in c[0]:
        for j in c[1]:
            if j in Adj_liste[i]:
                poids += 1
    return poids
# ------------------------------------------------------------------------------
def Temp_init(taux_acc,c):
    temp = [ arete_inter(c) for i in range(100) ]
    temp.sort()
    return sum( temp[-1-i] for i in range(20) )/20/log(1./taux_acc)
# ------------------------------------------------------------------------------
def dec_temp(t,coef):
    t = coef*t
    return t
# ------------------------------------------------------------------------------
def pick_and_drop(c):
    c1,c2 = c[0][:],c[1][:]
    n = randint(1,2)
    if (n == 1) and (len(c1)>int(nb_sommet/2)-p):
        a = choice(c1)
        c2.append(a)
        c1.remove(a)
    elif (n == 2) and (len(c2)>int(nb_sommet/2)-p):
        a = choice(c2)
        c1.append(a)
        c2.remove(a)
    else:
        if (len(c1)>int(nb_sommet/2)-p):
            a = choice(c1)
            c2.append(a)
            c1.remove(a)
        else:
            a = choice(c2)
            c1.append(a)
            c2.remove(a)  
    c1.sort()
    c2.sort()
    return c1,c2
# ------------------------------------------------------------------------------
def sweep_and_swap(c):
    c1,c2 = [],[]
    c1.extend(c[0])
    c2.extend(c[1])
    temp1 = choice(c1)
    temp2 = choice(c2)
    c1.remove(temp1)
    c2.remove(temp2)
    c1.append(temp2)
    c2.append(temp1)
    c1.sort()
    c2.sort()
    return c1,c2
# -----------------------------------------------------------------------------
def matrice_en_liste(Adj):
    """Convertit une matrice d'adjacence en liste d'adjacence."""
    adj_liste = []
    v = []
    n = len(Adj)
    for i in range(n):
        adj_liste.append([])
        v.append(i)
        for j in range(n):
            if (Adj[i][j] == 1) and (j not in v):
                adj_liste[i].append(j)
    return adj_liste
# ==============================================================================                   
def main():
    global nb_sommet, Adj_liste, taux_acc, coef, p, gel, equil_stat
 
    fichier = raw_input ("Quel fichier souhaitez-vous utiliser?")
    f = open(fichier,"r")
    donnees = f.read()
    nb = donnees.split()
    nb_sommet = int(nb[0])
    nb_arete = int(nb[1])
    print "Le nombre de sommet est ",nb_sommet, "Le nombre d'arêtes est ",nb_arete
    f.close()
    liste1=[]
    liste2=[]
    p=int(nb_sommet*0.01)+1
    for i in range(nb_arete):
        liste1.append(nb[2+3*i])
        liste2.append(nb[3+3*i])
    Adj = [[0 for j in range(nb_sommet)] for i in range(nb_sommet)]
    for i in range(nb_arete):
        Adj[int(liste1[i])-1][int(liste2[i])-1]=1
        Adj[int(liste2[i])-1][int(liste1[i])-1]=1
 
    Adj_liste = matrice_en_liste(Adj)
    courante = complementaire()
    poids = arete_inter(courante)
    taux_acc = raw_input("Donnez la valeur du taux acceptation si vous souhaitez?(par défaut il vaut 0.6)")
    if taux_acc == '':
        taux_acc = 0.6
    else:
        taux_acc = float(taux_acc)
    coef = raw_input("Donnez la valeur du coefficient de décroissance de la température si vous souhaitez?(par défaut il vaut 0.9)")
    if coef == '':
        coef = 0.9
    else:
        coef = float(coef)
    print dec_temp(Temp_init(taux_acc,courante),coef)
    equil_stat = nb_sommet
    gel = raw_input("Donnez la valeur pour laquelle on estime que le système est gelé?(par défaut elle vaut 60)")
    if gel == '':
        gel = 60
    else:
        gel = int(gel)
 
    poids = arete_inter(courante)
    t = Temp_init(taux_acc,courante)
    print t
    Ncourante = pick_and_drop(courante)
    solution = courante
 
 
    choix = raw_input("tapez 1 si vous voulez utiliser le pick_and_drop, taper 2 si vous voulez utiliser le sweep_and_swap")
    temps = time.time ()
    if choix == '1':
 
        while gel>0:
            k = 0
            while k<equil_stat:
                k += 1
                Ncourante = pick_and_drop(courante)
                delta = arete_inter(Ncourante) - arete_inter(courante)
                if delta<0:
                    courante = Ncourante
                    if arete_inter(Ncourante)<poids:
                        poids = arete_inter(Ncourante)
                        solution = Ncourante
                else:
                    a = random()
                    if a<=exp(-delta/t):
                        courante = Ncourante
            t = t*coef
            gel -= 1
            print gel
    if choix == '2':
 
        while gel>0:
            k = 0
            while k<equil_stat:
                k += 1
                Ncourante = sweep_and_swap(courante)
                delta = arete_inter(Ncourante) - arete_inter(courante)
                if delta<0:
                    courante = Ncourante
                    if arete_inter(Ncourante)<arete_inter(solution):
                        poids = arete_inter(Ncourante)
                        solution = Ncourante
                else:
                    a = random()
                    if a<=exp(-delta/t):
                        courante = Ncourante
            t = t*coef
            gel -= 1
            print gel         
 
    print "le temps mis par l'algo est", (time.time () - temps)       
    print "la meilleure solution trouvée est:  " ,solution
    print "Le poids est: " ,poids
    print "Le nombre d'itération est: " ,k
 
if __name__ == "__main__":
    main()
 
# ============================================================================

Le problème est que le poids retourner au final est de 0.

02/04/2010, 13h42
miawaw
ok donc c'est plutot comme avait dit josmiley.
Ben c'est facile de modifier ta fonction:
Code:

1 2 3 4 5 6 7 def arete_inter(c): poids = 0 for i in c[0]: for x in Adj_liste[i]: if x in c[1]: poids += 1 return poids
Le poids fait 40, maintenant. J'ai vérifier à la main. C'est correct.
Tu peux optimser:
Code:

1 2 3 4 5 6 def arete_inter(c): poids = 0 setC1 = set(c[1]) for i in c[0]: poids += len(setC1 & set(A[i])) return poids
et surprise ,c'est à peu près deux fois plus rapide que la fonction ci-dessus avec deux boucles. Moins de boucles et plus de fonctions prédéfinies = :ccool:

Pour ton programme complet, je ne peux rien faire car il me demande la lecture d'un fichier (que je n'ai pas).

Si tu imprimes la valeur de poids, à l'intérieur de la boucle juste après avoir incrémenté poids, que vois-tu ?

1 pièce(s) jointe(s)

ça me retourne comme valeur finale 0.
J'ai trouvé une alternative mais assez couteuse.
Code:

1 2 3 4 5 def arete_inter(c): poids1 = sum(1 for i in c[0] for j in c[1] if j in Adj_liste[i])+sum(1 for i in c[1] for j in c[0] if j in Adj_liste[i]) poids2 = sum(1 for i in c[1] for j in c[0] if j in Adj_liste[i]) poids = poids1 + poids2 return poids1
quand je fais un print aprés l'incrémentation, les valeurs de poids diminue jusqu'à atteindre 0.

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
28
29
30
31
32
c =  ([0, 2, 3, 5, 6, 7, 8, 11, 13, 17],
      [1, 4, 9, 10, 12, 14, 15, 16, 18, 19])
 
print 'c[0] =',c[0]
print 'c[1] =',c[1]
 
Adj_liste =  [[1, 2, 5, 6, 8, 10, 14, 16, 17, 18],
              [2, 3, 6, 7, 9, 10, 12, 13, 6, 9, 16, 18],
              [8, 10, 14, 15, 16, 17, 18],
              [7, 9, 11, 12, 13, 15, 16, 17],
              [8, 10, 12, 13, 14, 16, 18],
              [9, 10, 12, 13, 14, 16, 18],
              [10, 14, 17, 18],
              [11, 13, 14, 15, 17, 18],
              [12, 15, 17, 18],
              [14, 16, 17, 18],
              [15, 16, 17, 18],
              [], [], [18], [18], []]
 
print '\nAdj_liste =\n','\n'.join(repr(u) for u in Adj_liste)
print
 
for i in c[0]:
    poids = 0
    if i<len(Adj_liste):
        L = Adj_liste[i]
        for j in c[1]:
            if j in L:
                poids += 1
        print 'i =',i,'  poids =',poids
    else:
        print "Pas de sous-liste d'index",i,'dans Adj_liste'

Code:

1
2
3
4
5
6
7
8
9
10
i = 0   poids = 5
i = 2   poids = 5
i = 3   poids = 4
i = 5   poids = 6
i = 6   poids = 3
i = 7   poids = 3
i = 8   poids = 3
i = 11   poids = 0
i = 13   poids = 1
Pas de sous-liste d'index 17 dans Adj_liste

De façon plus pythonienne:

Code:

1
2
3
4
5
6
7
for i in c[0]:
    if i<len(Adj_liste):
        L = Adj_liste[i]
        poids = sum(1 for j in c[1] if j in L)
        print 'i =',i,'  poids =',poids
    else:
        print "Pas de sous-liste d'index",i,'dans Adj_liste'

Et en regroupant les résultats dans une liste:

Code:

1
2
POIDS = [ sum(1 for j in c[1] if j in Adj_liste[i]) if i<len(Adj_liste) else None for i in c[0] ]
print 'POIDS =',POIDS

Code:

POIDS = [5, 5, 4, 6, 3, 3, 3, 0, 1, None]

Code:

1
2
3
4
5
6
7
8
POIDS = [ sum(1 for j in c[1] if j in Adj_liste[i]) if i<len(Adj_liste) else None for i in c[0] ]
print 'POIDS =',POIDS
 
couples_i_POIDS = zip(c[0],POIDS)
print '\ncouples_i_POIDS =\n[ '+'\n  '.join(repr(u) for u in couples_i_POIDS),' ]'
 
dicoPOIDS = dict(zip(c[0],POIDS))
print '\ndicoPOIDS =\n',dicoPOIDS

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
POIDS = [5, 5, 4, 6, 3, 3, 3, 0, 1, None]
 
couples_i_POIDS =
[ (0, 5)
  (2, 5)
  (3, 4)
  (5, 6)
  (6, 3)
  (7, 3)
  (8, 3)
  (11, 0)
  (13, 1)
  (17, None)  ]
 
dicoPOIDS =
{0: 5, 2: 5, 3: 4, 5: 6, 6: 3, 7: 3, 8: 3, 11: 0, 13: 1, 17: None}

02/04/2010, 17h54
hyuga33
eyquem j'ai essayé ton code mais ça me retourne encore et toujous une solution finale poids=0.
J'arrive au résultat voulus avec cette fonction:
Code:

1 2 3 4 5 def arete_inter(c): poids = sum(1 for i in c[0] for j in c[1] if j in Adj_liste[i]) + sum(1 for i in c[1] for j in c[0] if j in Adj_liste[i]) return poids
Mais l'algo mets plus de temps à tourner avec les listes d'adjacence qu'avec la matrice d'adjacence. Or avec la matrice on peut difficilement dépasser les graphes ayant plus de 1000 sommets alors que je suis censé faire tourner l'algo sur des graphes ayant au moins 10 000 voire 100 000 sommets. Normalement avec les listes ça devait aller plus vite..

Citation:
Envoyé par eyquem
Code:

1 2 3 4 5 6 7 8 9 10 11 12 ... for i in c[0]: poids = 0 if i<len(Adj_liste): L = Adj_liste[i] for j in c[1]: if j in L: poids += 1 print 'i =',i,' poids =',poids else: print "Pas de sous-liste d'index",i,'dans Adj_liste'
...
Ooh lala, dans la fonction ci-dessus, l'instruction poids = 0 devrait être en dehors de la boucle for i in c[0]. hyuga33, tu fais ça et ça devrait marcher. (t'aimes pas ma fonction au fait? :calim2:)

02/04/2010, 18h26
hyuga33

merci miawaw, j'aime bien ta fonction mais je la comprends pas très bien. J'ai pas bien compris ce que retourne la fonction set(). Je vais essayer la modification que tu viens d'apporter. Merci.
02/04/2010, 18h40
hyuga33
Bon j'ai fait tourner et je resort toujours 0.
Du coup j'ai tester l'ajout d'une autre boucle
Code:

1 2 3 4 5 for i in c[1]: L = Adj_liste[i] for j in c[0]: if j in L: poids += 1
et là ça marche. Je trouve poids = 40 ou 39(ça dépend des fois).
Sur toute les formulations que j'ai essayé, l'algo marche correcement que si je rajoute ce genre de boucle. Je ne comprends pas trop pourquoi.
02/04/2010, 19h49
miawaw
Citation:

Envoyé par hyuga33

merci miawaw, j'aime bien ta fonction mais je la comprends pas très bien. J'ai pas bien compris ce que retourne la fonction set(). Je vais essayer la modification que tu viens d'apporter. Merci.

alors en fait, comme son nom l'indique, set est un type de base(built-in) se comportant comme un ensemble. Si s1 et s2 sont deux ensembles, on peut effectuer les operations suivantes:
s1.difference(s2)
s1.union(s2)
s1.intersection(s2)
s1.issubset(s2)
... (voir la documentation)

(cf les equivalents: intersection <-> operateur &, union <-> operateur |,...)

Contrairement aux listes, si un élément x est déjà dans un ensemble s, alors ajouter x à s ne modifie rien du tout. Les 'set' contiennent un élément en un seul exemplaire.

Code:

L = list(set(L))

permet par exemple de tuer tous les doublons dans la liste L.
Je rappelle ma fonction:
Code:

1 2 3 4 5 6 def arete_inter(c): poids = 0 setC1 = set(c[1]) for i in c[0]: poids += len(setC1 & set(Adj_list[i])) return poids
Cela fait bien le travail qu'on lui demande: connaitre pour chaque i dans c[0], les éléments qui sont à la fois dans Adj_list[i] et dans c[1]. Donc cela revient à compter le nombre d'éléments se trouvant dans l'intersection de deux ensembles d'indices. (s1.intersection(s2) est équivalent à s1 & s2)
Je ne peux calculer une intersection qu'entre deux ensembles, voila pourquoi je crée l'ensemble setC1 (à l'extérieur du for). Le nombre d'éléments à l'intersection de setC1 et set(Adj_list[i]) est calculable facilement :

Code:

len(setC1 & set(Adj_list[i]))

D'accord, j'ai enfin compris.
Si je laisse le code tel que tu me l'a donné, l'algo me retourne 0 mais si je fais en plus l'intersection entre c[0] et Adj_liste alors ça marche.
Donc voici mon code final pour ma fonction:
Code:

1 2 3 4 5 6 7 8 9 def arete_inter(c): poids = 0 setC1 = set(c[1]) setC0 = set(c[0]) for i in c[0]: poids += len(setC1 & set(Adj_liste[i])) for i in c[1]: poids += len(setC0 & set(Adj_liste[i])) return poids
Je perds en complexité par rapport à la première version de mon programme qui utilisait juste une matrice au lieu de liste.
Merci beaucoup pour tes conseils.

Je ne suis toujours pas arrivé à comprendre ce que tu recherches comme résultat

Peux tu donner les calculs que tu ferais à la main pour trouver poids avec les données suivantes stp:
Code:

1 2 3 4 5 6 7 8 9 c = ([0, 2, 3, 5], [1, 4]) Adj_liste = [[1, 2, 5, 6, 8], [2, 3, 6, 7], [8, 10, 14], [7, 9, 11, 12], [3, 8], [1, 9, 10]]
Je me demande si tu ne comptes pas deux fois certaines valeurs avec ton dernier code.

désolé de ne pas avoir répondu plus tôt, je rentre du boulot ...
voilà ce que je propose si j'ai bien tout compris:
c[0] ne sert à rien ici, puisque de toute façon on parcourt entierement Adj_liste.
on ne va donc pas chercher les elements de Adj_list dans c[1], mais plutôt le contraire.

Code:

1
2
3
4
5
6
c =  ([0, 2, 3, 5, 6, 7, 8, 11, 13, 17], [1, 4, 9, 10, 12, 14, 15, 16, 18, 19])
Adj_liste =  [[1, 2, 5, 6, 8, 10, 14, 16, 17, 18], [2, 3, 6, 7, 9, 10, 12, 13, 14, 16, 17, 18], [3, 4, 5, 6, 7, 9, 14, 16, 17, 18], [4, 5, 11, 15, 16], [5, 6, 9, 16, 18], [8, 10, 14, 15, 16, 17, 18], [7, 9, 11, 12, 13, 15, 16, 17], [8, 10, 12, 13, 14, 16, 18], [9, 10, 12, 13, 14, 16, 18], [10, 14, 17, 18], [11, 13, 14, 15, 17, 18], [12, 15, 17, 18], [14, 16, 17, 18], [15, 16, 17, 18], [], [], [18], [18], []]
#si ce que tu veux c'est poids total
print sum([sum(Adj_liste,[]).count(x) for x in c[1]]) #>> 59
#si ce que tu veux c'est poids pour chaque sommet
print [sum(Adj_liste,[]).count(x) for x in c[1]] #>> [1, 2, 5, 6, 5, 9, 6, 11, 14, 0]

Voila ce que je compte faire(si c'est pas clair n'hésite pas à me demander, j'ai toujours eu du mal à expliquer):

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
28
29
30
31
32
33
34
c =  ([0, 2, 3, 5],
      [1, 4])
 
Adj_liste =  [[1, 2, 5, 6, 8],
              [2, 3, 6, 7],
              [8, 10, 14],
              [7, 9, 11, 12],
              [3, 8],
              [1, 9, 10]]
 
c[0]=[0,2,3,5]
c[1]=[1,4]
 
je parcours c[0]:(classe de sommet)
je prends le 1er sommet et si il est liée avec un des sommets ou plusieurs de c[1]
j ajoute 1 à poids.
Pour vérifié si ils sont liées je regarde Adj_liste.
poids = 0
pour i = 0;
je regarde [1,2,5,6,8]
1 est dans c[1] donc poids = 1
pour i = 2;
je regarde [8,10,14]
aucun des éléments est dans c[1] donc poids = 1
pour i = 3;
je regarde [7,9,11,12]
aucun des éléments est dans c[1] donc poids = 1
pour i = 5;
je regarde [1,9,10]
1 est dans c[1] donc j incrémente poids et poids = 2
 
 
Normalement, c comprens tout les sommets. Ici, c = ([0,2,3,5,7,8,14],[1,4,6,9,10,11,12,13])
aurait été plus en rapport.

Avant mon dernier code je regardais juste dans un sens(c[0] "vers" c[1]).
Avec le dernier je vais dans les deux sens. c'est possible que j'en compte en double mais j'ai retrouvé les résultats que je trouve sur ma première version.

Voir 40 message(s) de cette discussion en une page