Je vous propose aujourd'hui de résoudre un problème algorithmique en Python, très largement inspiré d'un chapitre de l'excellent livre Pearls of Functional Algorithm Design de Richard Bird.
Formulation du problème
Vous assistez à une soirée où sont présentes un certain nombre de personnes.
La classe Person
Une personne se caractérise par son nom, ainsi que la liste des noms des personnes qu'elle connaît. Elle dispose d'une méthode knows, permettant de savoir si elle connaît la personne qui lui est passée en paramètre :
a.knows(b) retourne :
True si la personne a connaît la personne b,
False si a ne connaît pas b.
La relation knows n'est pas symétrique : une personne a peut tout à fait connaitre une personne b alors que b ne connaît pas a.
Voici le code de la classe Person
class Person(object):
def __init__(self, name):
self.name = name
self._known = []
def knows(self, other):
return other.name in self._known
def __str__(self):
return str(self.name)
def __repr__(self):
return repr(self.name)
Faites entrer les VIP
Parmi les gens qui assistent à la soirée, vous avez un certain nombre (strictement positif) de VIP.
Voici les propriétés des VIP :
Un VIP ne connaît que les autres VIP, il ne connait pas de gens ordinaires. (On appelle cela une "clique" en théorie des graphes)
Un VIP est connu de tout le monde,
Ainsi, vous avez dans cette soirée un groupe de VIP qui se connaissent tous entre eux, qui sont connus de tout le monde, mais qui ne connaissent personne en dehors de leur groupe.
Votre mission, si vous l'acceptez
Le but de cet exercice, est de rechercher, étant donnée la liste de toutes les personnes assistant à cette soirée, cette clique de VIP.
Voici une fonction qui crée une liste d'invités pour tester votre algorithme :
from random import shuffle, randrange, sample
def mk_problem():
# Création de la clique de VIP (j'avais pas d'inspiration pour les
# célébrités, et comme je suis en train d'écouter du jazz...)
c_names = ["Louis Armstrong", "Oscar Peterson", "Billie Holiday",
"Ella Fitzgerald", "Paul Desmond", "Chet Baker",
"Dave Brubeck", "Niels E.H. Pedersen", "John Pass",
"Quincy Jones"]
c_clique = [Person(n) for n in c_names]
# Les VIP se connaissent tous entre eux
for c in c_clique:
c._known = c_names
# Création d'un certain nombre de gens ordinaires
n_names = ["Toto", "Titi", "Tata", "Tutu", "Bibi", "Coco", "Papi", "Tati",
"Dede", "Dudu", "Bobo"]
normal_people = [Person(n) for n in n_names]
# Les gens normaux connaissent tous les VIP
# ainsi qu'un certain nombre d'autres gens normaux (choisis au hasard).
for n in normal_people:
n._known = c_names + sample(n_names, randrange(len(n_names)))
# On mélange le tout
party = normal_people + c_clique
shuffle(party)
return party
Votre mission est donc de créer une fonction find_vip qui prend en argument la liste des personnes assistant à la soirée (dans l'exemple : le retour de la fonction mk_problem, et retourne la liste des VIP de cette soirée).
Le but de cet exercice est de trouver un algorithme efficace permettant de résoudre ce problème (en formulant l'hypothèse qu'il y a une et une seule clique de VIP à cette soirée) en ne se servant que de la méthode knows. L'algorithme naïf est en O(nk) en termes d'utilisation de l'opérateur knows avec n le nombre de personnes assistant à la soirée et k le nombre de VIP. Il est possible de faire BEAUCOUP mieux que ça. Une première amélioration de l'algorithme naïf (tenant compte des contraintes sur les VIP) est en O(n²), et il existe une solution linéaire (en O(n)) à ce problème.
Voici une seconde fonction de test (python 2 ET 3), permettant de tester les performances de votre fonction avec possibilité de dimensionner le problème :
total est le nombre total d'invités à la soirée.
vips est le nombre de vips (< total).
functions est la liste des fonctions à tester.
from __future__ import print_function
from random import shuffle, sample, randrange
from time import time
def test_function(total, vips, functions):
print("Building list of {0} vips and {1} normal people".format(vips
, total - vips))
vip_names = set(range(vips))
normal_names = set(range(vips, total))
vip = [Person(c) for c in vip_names]
normal = [Person(p) for p in normal_names]
for v in vip:
v._known = vip_names
for p in normal:
p._known = vip_names.union(sample(normal_names, randrange(vips)))
party = vip + normal
shuffle(party)
for fn in functions:
print("Running '{0}' :\t".format(fn.__name__), end=" ")
start = time()
result = fn(party)
end = time()
print("[{0:.6f}s]".format(end-start), end= " ")
result.sort(key=lambda p:p.name)
print("OK" if result == vip else "FAIL!")
Bon courage !
Je posterai une première solution en O(n²) dans 24h si personne n'a le courage d'essayer d'ici-là.
Ainsi, vous avez dans cette soirée un groupe de VIP qui se connaissent tous entre eux, qui sont connus de tout le monde, mais qui ne connaissent personne en dehors de leur groupe. On appelle cela une "clique".
Non, ce n'est pas ce qu'on appelle une clique car tu as ajouté une condition très forte, à savoir que les VIP sont connus de tout le monde. Dans ces conditions, le problème est trivial, il suffit de chercher tous les sommets de degré entrant n-1 où n est le nb total de personnes et c'est alors forcément une clique puisque si a et b sont deux tels sommets, par hypothèse sur a et b, a et b se connaissent mutuellement. Trouver tous les sommets de degré n-1 est une opération en n**2 (et pas moins, imagine que tout ton groupe ne soit constitué que de VIP, autrement dit que le graphe soit complet). Quand tu disais linéaire, tu voulais peut-être dire en le nombre d'arêtes mais attention, le nombre d'arêtes peut s'approcher de n*2 donc c'est de la fausse linéarité.
Sinon, je trouve dommage de cacher un problème d'algorithmique dans un contexte assez lourd de POO.
Oui, il y a une contrainte très forte (ainsi qu'une autre contraite qui veut qu'il y ait nécessairement un groupe de VIP), justement pour garantir l'unicité de cette clique et faire en sorte que le problème ne soit pas NP-complet (rechercher la clique la plus grande).
Sinon, quand je dis linéaire, c'est bel et bien linéaire en le nombre de sommets (de personnes).
Citation : candide
Sinon, je trouve dommage de cacher un problème d'algorithmique dans un contexte assez lourd de POO.
Si j'ai défini une classe Person moi-même, c'est justement pour que l'on utilise tous la même représentation : la fonction utilise simplement l'opérateur knows de la classe Person, de façon opaque en considérant qu'il s'agit d'une opération élémentaire (les set en Python permettent d'ailleurs d'obtenir une complexité en O(1) sur cette méthode) : nul besoin de connaître la POO pour résoudre cet exo, donc.
Edit : j'ai précisé l'énoncé (pour ne pas mal définir le terme de clique) ainsi que le sous-titre (recherche d'une clique particulière)
Edit2 : Puisque tu as donné la solution en O(n2), la voici :
def vip_gen(persons):
return (p for p in persons if all(k.knows(p) for k in persons))
def find_vip_quad(persons):
return list(vip_gen(persons))
Cette solution calcule le résultat sur un problème à 10000 personnes (dont 500 VIP), sur ma machine, en 5.222 secondes.
Une amélioration directe de cet algorithme permet de le rendre "presque" linéaire, le faisant s'exécuter, sur le même problème, en 0,019 seconde.
La solution linéaire, quant à elle, prend sur ma machine 0,016 seconde.
def find_vip(party):
fiesta = party[:]
for person in fiesta:
for otherperson in fiesta[:]:
if not person.knows(otherperson): fiesta.remove(otherperson)
return fiesta
Building list of 500 vips and 9500 normal people
Running 'find_vip_quad': [5.146332s] OK
Running 'find_vip_josmiley': [0.401770s] OK
Running 'find_vip_better': [0.018467s] OK
Running 'find_vip_linear': [0.017028s] OK
Par contre, en augmentant la proportion de VIP et le nombre de connaissances des gens ordinaires :
Building list of 5000 vips and 5000 normal people
Running 'find_vip_quad': [45.618220s] OK
Running 'find_vip_josmiley': [17.350655s] OK
Running 'find_vip_better': [0.017984s] OK
Running 'find_vip_linear': [0.017059s] OK
Salut, je propose une solution linéaire à cet exercice intéressant.
Il s'agit de parcourir la liste des personnes une première fois: pour chaque personne, si elle connaît la suivante on continue normalement, sinon on supprime celle-ci (elle n'est forcément pas VIP) et on recommence. La dernière personne de la liste ainsi traitée est forcément un VIP, on n'a plus qu'à renvoyer la liste filtré en fonction des connaissances de ce VIP.
On utilise entre n+k (meilleur des cas) et 2n (pire des cas) fois la méthode knows, la solution est donc linéaire.
def vips(party):
i,l=0,party[:]
while i<len(l)-1:
if l[i].knows(l[i+1]): i+=1
else : del l[i+1]
return filter(l[-1].knows,l)
Building list of 500 vips and 9500 normal people
Running 'find_vip_quad' : [3.808000s] OK
Running 'find_vip_josmiley' : [0.356000s] OK
Running 'vips' : [0.037000s] OK
Le principe "trouver le premier VIP dont on est sûr, et retourner la liste de ses connaissances" est celui de la fonction "find_vip_better".
Ici, on cherche le premier VIP "à la brutor" (la première personne connue de toutes les autres que l'on trouvera dans la liste), et on retourne ses connaissances :
def vip_gen(persons):
return (p for p in persons if all(k.knows(p) for k in persons))
def find_vip_better(persons):
v = vip_gen(persons).next()
return [p for p in persons if v.knows(p)]
La première phase est donc un O(n²) (mais qui termine dès qu'on a trouvé le premier VIP, donc assez rapidement), et la seconde un O(n).
Voilà le comparatif :
Building list of 500 vips and 9500 normal people
Running 'find_vip_quad': [5.209512s] OK
Running 'find_vip_josmiley': [0.279171s] OK
Running 'find_vip_EMC1': [0.027112s] OK
Running 'find_vip_better': [0.018381s] OK
Running 'find_vip_linear': [0.016826s] OK
Et en corsant un peu le problème :
Building list of 5000 vips and 5000 normal people
Running 'find_vip_quad': [45.551293s] OK
Running 'find_vip_josmiley': [18.044011s] OK
Running 'find_vip_EMC1': [0.024511s] OK
Running 'find_vip_better': [0.017652s] OK
Running 'find_vip_linear': [0.018022s] OK
Ta fonction est donc robuste aux variations en proportion de VIP et en nombre de connaissances des individus lambda.
Reste à déterminer une solution linéaire qui ne nous oblige pas à connaître un VIP dès le départ.
Wow : cette fonction est vachement rapide, bien joué, tu passes en tête !
Building list of 500 vips and 9500 normal people
Running 'find_vip_EMC1': [0.026495s] OK
Running 'find_vip_better': [0.018644s] OK
Running 'find_vip_linear': [0.017147s] OK
Running 'find_vip_josmiley2': [0.009718s] OK
Par contre, en "corsant" le problème, elle ralentit, et devient en moyenne aussi rapide que les autres.
Building list of 5000 vips and 5000 normal people
Running 'find_vip_EMC1': [0.022855s] OK
Running 'find_vip_better': [0.017416s] OK
Running 'find_vip_linear': [0.017006s] OK
Running 'find_vip_josmiley2': [0.020505s] OK
Building list of 5000 vips and 5000 normal people
Running 'find_vip_EMC1': [0.022959s] OK
Running 'find_vip_better': [0.018132s] OK
Running 'find_vip_linear': [0.017884s] OK
Running 'find_vip_josmiley2': [0.013481s] OK
Super efficace quand il n'y a pas beaucoup de VIP ou peu de relations "knows" entre les individus normaux.
Reste à déterminer une solution linéaire qui ne nous oblige pas à connaître un VIP dès le départ.
????
Une solution linéaire en n n'existe pas puisque si la réunion d'individus est composée uniquement de n VIP, tu auras une clique de <math>\(n^2\)</math> et donc ton algo ne peut pas faire moins. Par contre, il peut être linéaire en n et m ou m est le nombre d'arêtes du graphe des connaissance. Mais bon, rien de difficile, comme j'ai dit, il suffit de chercher les personnes connues de toutes (sauf éventuellment d'elle-même) donc la complexité de l'algo est exactement de n + m, c'est une banale boucle :
connait=[
[3,5,2,0],
[3,5,4,0,1],
[3,5,1],
[5,0],
[3,5,4],
[3,1,2,4]
]
def vip(n,connait):
t=[0]*n
for p in connait:
for c in p:
t[c]+=1
return [i for i in range(n) if t[i]==n-1]
print vip(6,connait)
[3, 5]
Bien sûr, on peut faire de micro-optimisation, par exemple il est inutile de parcourir une liste d'un individu qui n'apparait pas dans une liste de connaissances déjà rencontrée. En pratique, ça peut bien sûr accélérer mais ça ne change pas la complexité algorithmique.
Cette solution est assez laborieuse en Python, le plus efficace est d'utiliser des ensembles :
connait=[
[3,5,2,0],
[3,5,4,0,1],
[3,5,1],
[5,0],
[3,5,4],
[3,1,2,4]
]
def vip_set(n,connait):
z=set(range(n))
for i in range(n):
z&=set(connait[i])|set([i])
return list(z)
print vip_set(6,connait)
def find_vip_linear(persons):
vip, v = [], None
for p in persons:
if v is None or not p.knows(v):
vip = [p]
v = p
elif v.knows(p):
vip.append(p)
return vip
L'idée, c'est de se mettre un peu "à la place du videur", et d'intercepter les gens qui "entrent".
On prend la première personne qui vient, et on fait l'hypothèse que c'est un VIP. On l'appelle V.
Ensuite, à chaque personne P qui entre : si P ne connaît pas V, c'est que V n'est pas un VIP, donc P remplace V, et [P] remplace la "clique" de V.
Si P connaît V, et que V connaît P, alors, par hypothèse, P est aussi un VIP, donc on l'ajoute à la clique de V. Sinon, V ne connaît pas P, donc P est forcément un individu lambda et on l'ignore.
Une fois que toutes les personnes sont entrées, on est forcément tombé sur un VIP, donc la clique que l'on a construite est forcément la clique de VIP que l'on cherche (à cause des contraintes de l'énoncé sur les VIP).
Au final, en termes d'utilisation de l'opérateur knows() (dont l'implémentation par les set est en O(1), je le rappelle, quoiqu'il est possible de faire la même chose avec une LUT) :
Pour chaque personne (×N):
- évaluation de p.knows(v)
- évaluation éventuelle de v.knows(p)
On trouve le résultat en 2N utilisation de knows (où N est le cardinal de l'ensemble des sommets). Je sais pas pour toi, mais moi j'appelle ça une complexité linéaire.
Au final, en termes d'utilisation de l'opérateur knows() (dont l'implémentation par les set est en O(1),
Eh, non tout le problème est là. Une application known comme tu dis ça s'appelle une matrice d'adjacence, ça a une taille de <math>\(n^2\)</math>. Imagine, comment tu fais pour connaître le graphe des connaissances de ta party :
tu prends Toto et tu lui demandes :
- Toto, connais-tu TaTa ? Rép : Non
- Toto, connais-tu TuTu ? Rép : Oui
- Toto, connais-tu Sarko ? Rép : Oui
etc
et tu recommences avec chacun des individus, ce qui fait n*(n-1) requêtes ce qui est un <math>\(O(n^2)\)</math>.
Ensuite, l'énoncé parle bien dès le départ de complexité en termes d'utilisation de l'opérateur knows, ce qui fait que tu pars du principe que tu as déjà créée ta matrice d'adjacence (ou toute représentation valable), donc que tu considères dans le calcul de complexité que la complexité théorique de knows est O(1) de toute façon.
@Candide: Tu prends une matrice de taille n*n de booléen que tu remplit avant, tu numérotes les personnes, et knows n'est plus qu'en accés à la dite case : ie constant. Ou dit autrement tu changes la représentation des données et à la place d'une liste de personne connu tu prends un tableau de bolléen. Et de toute facon l'énoncé était en terme d'appel à knows.
Ensuite, l'énoncé parle bien dès le départ de complexité en termes d'utilisation de l'opérateur knows, ce qui fait que tu pars du principe que tu as déjà créée ta matrice d'adjacence (ou toute représentation valable), donc que tu considères dans le calcul de complexité que la complexité théorique de knows est O(1) de toute façon.
Oui, dans ces conditions la complexité est linéaire et la solution est assez futée, je dois reconnaître, merci de nous l'avoir fait connaître.
Pour essayer de faire parler un peu plus les chiffres, et se faire une meilleure idée des performances des solutions proposées, je me suis amusé à benchmarker les 4 algos (celui d'EMC1, le second de josmiley, le "better", et le "linear"), et à tirer les graphes correspondants.
J'ai fait pour cela 5 sessions (en faisant varier N entre 1000 et 15000), avec une population de vip représantant respectivement 90%, 80%, 70%, 60%, et 50% de la population totale.
La méthode knows, dans ces conditions, est l'opérateur in sur les set, qui a bien une complexité moyenne en O(1).
Les relations de connaissance entre individus lambda sont décidées par tirage au sort (chaque individu connait un nombre arbitraire de gens lambda, pris au hasard entre 0 et le nombre de gens lambda de la population).
Dans le cas extrême, (50% vip, N=14000 et plus), il faut avouer que ça fait un peu chauffer le silicium (tellement que l'on a des énormes outliers) vu le nombre extrêmement conséquent de relations entre les individus lambda (c'est une combinatoire...).
Voilà les résultats.
90% de VIP
80% de VIP
70% de VIP
60% de VIP
50% de VIP
Sur ce dernier graphe, j'ai retiré les 2 derniers résultats pour l'algo de EMC1 et le "better", le premier passant directement à 1.4s pour N=14000 (donc le reste du graphe serait ratatiné), et 0.3s pour N=15000, et le second prenant 15 secondes juste pour le cas N=14000, et 27s pour N=15000 (ce qui signifie grosso-modo que le O(n²) de la phase de recherche du premier VIP rattrape le O(n) du reste de l'algo).
On remarque que l'algorithme de josmiley est souvent plus rapide, mais très instable.
Je conjecture que certains pètes en performances sont pris en raison des allocations de liste...
Edit : pour essayer de comprendre l'instabilité de l'algo de josmiley, j'ai essayé un autre cas extrême, c'est à dire un bench avec N variant entre 100 et 3000, avec 10% de VIP.
Ça ne vient en fait probablement pas des allocations de mémoire...
def find_vip_linear(persons):
vip, v = [], None
for p in persons:
if v is None or not p.knows(v):
vip = [p]
v = p
elif v.knows(p):
vip.append(p)
return vip
Une variante de ta méthode qui m'a permis de comprendre plus facilement l'algo. Le code est plus simple mais curieusement les performances un poil moins bonnes. De plus en plus, je trouve assez lourd le for de Python, ya qu'à voir les contorsions que ça m'oblige à faire. Ah ! rien ne vaut le bon vieux C.
def find_vip_candide(persons):
z=iter(persons) # ces deux lignes juste pour
q=z.next() # commencer au 2ème terme de la liste
for p in z:
if not p.knows(q):
q=z.next()
return [p for p in persons if q.knows(p)]
J'ai testé sur le "bench 70%", je ne vois pas de différence notoire de performances avec mon implémentation.
L'algo est un peu différent, mais ça revient bien à choisir un VIP en O(n) itérations maximum puis reconstruire la clique avec une list comprehension en O(n), donc un algo parfaitement linéaire.
Par contre, à quelques instabilités près, la nouvelle implémentation de josmiley est vraiment pas mal non plus.
Jolis et convaincants ces petits graphiques, c'est du matplotlib, non ?
Citation : NoHaR
Par contre, à quelques instabilités près, la nouvelle implémentation de josmiley est vraiment pas mal non plus.
Ça se comprend assez bien puisque son algo peut terminer bien avant d'avoir tout parcouru ce qui n'est pas le cas de ton algo. Mais, dans certains cas (ça dépend du tirage), l'algo de josmiley est presque du quadratique. Pourtant, je suis étonné qu'il rivalise aussi bien avec celui de EMC1. Et l'avantage de l'algo de josmiley c'est qu'il est compréhensible assez rapidement (tout en étant assez élégant) tandis que le tien demande vraiment de se casser la tête pour comprendre que ça marche.
Jolis et convaincants ces petits graphiques, c'est du matplotlib, non ?
Tout à fait.
Citation : candide
Pourtant, je suis étonné qu'il rivalise aussi bien avec celui de EMC1. Et l'avantage de l'algo de josmiley c'est qu'il est compréhensible assez rapidement (tout en étant assez élégant) tandis que le tien demande vraiment de se casser la tête pour comprendre que ça marche.
Ça doit être avant tout une question d'habitudes, je suppose. J'ai justement le point de vue inverse sur la compréhension des programmes.
Il est aussi possible que l'algorithme de ma fonction me paraisse évident parce que je me suis cassé la tête à lire la preuve formelle de son fonctionnement (sa dérivation depuis l'algorithme naïf) en Haskell dans le livre de Richard Bird (raison pour laquelle, d'ailleurs, j'ai préféré utiliser la métaphore du videur en l'expliquant ici, parce que je la trouvais particulièrement adaptée).
Une variante de ta méthode qui m'a permis de comprendre plus facilement l'algo. Le code est plus simple mais curieusement les performances un poil moins bonnes. De plus en plus, je trouve assez lourd le for de Python, ya qu'à voir les contorsions que ça m'oblige à faire. Ah ! rien ne vaut le bon vieux C.
def find_vip_candide(persons):
z=iter(persons) # ces deux lignes juste pour
q=z.next() # commencer au 2ème terme de la liste
for p in z:
if not p.knows(q):
q=z.next()
return [p for p in persons if q.knows(p)]
Marrant, j'ai moi aussi modifié la fonction de cette manière, mais en plus lisible (sans contorsions ), comme ceci :
def find_vip_linear2(persons):
v = persons[0]
for p in persons[1:]:
if not p.knows(v):
v = p
return [p for p in persons if v.knows(p)]
Je suppose que tu as voulu éviter le persons[:1], qui crée une copie semble-il. Question: créer un itérateur est-il plus performant ? Et où trouve on ce genre d'informations ?
Citation : nohar
L'algo est un peu différent, mais ça revient bien à choisir un VIP en O(n) itérations maximum puis reconstruire la clique avec une list comprehension en O(n), donc un algo parfaitement linéaire.
Il y a globalement un avantage et un inconvénient :
Avantage : on ne crée pas de multiples listes de VIP théoriques (ça peut faire mal dans le cas ou les VIP sont en fin de liste)
Inconvénient : on parcourt la liste deux fois.
Pour moi, l'avantage est nettement plus intéressant (stabilité de l'algo).
Je sais que le topic est vieux mais je me permet de tenter ma chance.
Avant de commencer j'aimerais savoir: doit on generer aléatoirement le fait qu'une personne soit VIP soit non?
from random import choice, shuffle,randint
from time import time
class VIP:
liste=[]
def __init__(self,nom):
self.nom=nom
VIP.liste.append(self.nom)
def connaitre(self,pers):
if isinstance(pers,VIP):
return True
elif isinstance(pers,Normal):
return False
class Normal:
liste=[]
def __init__(self,nom):
self.nom=nom
Normal.liste.append(self.nom)
def connaitre(self,pers):
return True
def generer_fete(invités=["Louis Armstrong", "Oscar Peterson", "Billie Holiday",
"Ella Fitzgerald", "Paul Desmond", "Chet Baker",
"Dave Brubeck", "Niels E.H. Pedersen", "John Pass",
"Quincy Jones"]):
global var
fete=[]
for n in invités:
i=randint(0,1)
if i:
n=VIP(n)
else:
n=Normal(n)
fete.append(n)
shuffle(fete)
trouvés=False
for i in range(len(fete)-1):
if not fete[i].connaitre(fete[i+1]):
var=fete[i+1]
trouvés=True
break
if not trouvés:
for i in range(len(fete)-1,0,-1):
if not fete[i].connaitre(fete[i-1]):
var=fete[i+1]
break
return [n.nom for n in fete if not n.connaitre(var)]
-On parcourt la liste de gauche a droite et dés que fete[x] ne connait pas fete[x+1] on stocke fete[x+1] dans une variable global (oui je sais c'est mal ) et on arrete le for (car on sait que cette personne est non-vip)
-si malgré tout on ne trouve personne on refait la même chose mais en sens inverse
-ainsi on n'a plus qu'a renvoyer la liste des personnes qui ne connaissent PAS cette personne
dans le pire des cas on parcourt la liste 3 fois ce qui fait autour des O(3n)
def generer_fete(invités=["Louis Armstrong", "Oscar Peterson", "Billie Holiday",
"Ella Fitzgerald", "Paul Desmond", "Chet Baker",
"Dave Brubeck", "Niels E.H. Pedersen", "John Pass",
"Quincy Jones"]):
global var
fete=[choice([Normal,VIP])(n) for n in invités]
shuffle(fete)
trouvés=False
for i in range(len(fete)-1):
if not fete[i].connaitre(fete[i+1]) and all([n.connaitre(fete[i]) for n in fete]):
var=fete[i]
trouvés=True
break
if not trouvés:
for i in range(len(fete)-1,0,-1):
if not fete[i].connaitre(fete[i-1]) and all([n.connaitre(fete[i]) for n in fete]):
var=fete[i]
break
return [n.nom for n in fete if var.connaitre(n)]
j'ai donc légerement changé l'algorithme:
-on parcourt la liste de gauche a droite et si l'element a indice i ne connait pas l'element à l'indice i+1 et que i est connu de tout le monde alors on le met dans un variable car on sait que c'est un VIP.(on fait le parcours la liste en sens inverse si on ne trouve pas de VIP genre [Normal, Normal, Normal...VIP,VIP])
-on renvoit la liste des personnes que la personne "echantillon" connait
@Nohar connait fait tu pour voir le temps d'execution sur un grand nombre d'invités ?
- Edité par Smich74 3 juillet 2013 à 10:14:34
Si c'était facile, tout le monde le ferait.
[Exercice][Moyen - Avancé] Trouver les VIP
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.