Discussion :

[hyuga33]

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 :

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

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 :

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

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.

[miawaw]

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

[josmiley]

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

Code :

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

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 :

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

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 :

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

sum(liste,[])

[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.

[miawaw]

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

Code :

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

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 ?

[hyuga33]

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

Code :

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

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 :

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

[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]

[hyuga33]

Voici mon code en entier.

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
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.

[miawaw]

ok donc c'est plutot comme avait dit josmiley.
Ben c'est facile de modifier ta fonction:

Code :

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

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 :

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

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 =

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 ?

[eyquem]

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
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 :

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

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 :

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

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 :

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

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 :

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

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