Freunde innerhalb eines bestimmten Grades der Trennung erreichen

Question

alle. Ich bin ein sehr, sehr neuer Programmierer. Meine Sprache der Wahl ist momentan Python und ich habe das Gefühl, dass ich ein gutes Gefühl dafür habe. Ich lerne gerade erst von Rekursion. (Übrigens, wenn jemand eine gute Anleitung dazu empfehlen könnte, lassen Sie es mich bitte wissen!) Nur damit Sie alle wissen, diese Frage ist sehr elementar und der Code, den ich poste, ist furchtbar, entsetzlich falsch.

Wie auch immer, ich versuche eine Funktion zu schreiben, die alle Freunde innerhalb eines bestimmten Grades bekommt. Wenn ich es als Grad 0 gebe, will ich nur mich. Wenn ich es gebe 1, will ich mich und alle meine Freunde. 2, ich will mich, meine Freunde und all ihre Freunde und so weiter.

Ich habe versucht, einige verschiedene Möglichkeiten, dies zu tun, aber keine Arbeit. Ich versuche mir vorzustellen, wie es in der Theorie funktionieren soll, und ich kann das auch nicht ganz verstehen, weil ich auf diesem Gebiet so unerfahren bin. Vielleicht kann eine freundliche Seele mir hier alle Möglichkeiten aufzeigen, wie dieser Code versagt, und dann erklären, wie man es richtig macht und/oder eine gute Anleitung zu diesem Thema empfiehlt. Hier gehts:

Es funktioniert nicht, und ich weiß, ich habe dumme, dumme Dinge getan. Jemand klopft mich bitte und zeigt mir in die richtige Richtung!

Danke.

Answer 1

friendList = friendList.append(self) 

Dies setzt friendList-None, bedingungslos, wie das ist, der unveränderliche Rückgabewert jeder append Methode der Liste - so, fix dass Seltsamkeit ersten ... -)

Sobald Sie behoben, dass Sie immer noch die Funktion reparieren müssen, so dass es immer mit return von etwas endet - "vom Ende fallen" gibt None zurück. ZB:

def getFriends(self,degree, friendList): 
    if degree == 0: 
     friendList.append(self) 
     return friendList 
    else: 
     friendList.append(self) 
     for each in self.friends: 
      each.getFriends(degree-1, friendList) 
     return friendList 

welche und deutlich die Doppelarbeit zu beseitigen Refactoring werden soll, kann (DRY, Do not Repeat Yourself, ist das Herz der Programmierung ...):

def getFriends(self,degree, friendList): 
    friendList.append(self) 
    if degree > 0: 
     for each in self.friends: 
      each.getFriends(degree-1, friendList) 
    return friendList 

PS: dass (die alist=alist.append(...) Ausgabe) genau wie ich im Jahr 2002 wieder in Kontakt mit meiner Frau Anna kam (wir waren nicht-ganz-Schatz Freunde vor vielen Jahren aber hatten einander aus den Augen verloren) - sie begann Python zu studieren, genau verwendet Dieses fehlerhafte Konstrukt konnte nicht verstehen, warum es fehlgeschlagen war - sah sich in der Python-Gemeinschaft um, sah und erkannte meinen Namen , schickte mir eine Mail, um danach zu fragen ... weniger als zwei Jahre später waren wir verheiratet, und bald darauf war sie das erste weibliche Mitglied der Python Software Foundation und mein Co-Autor in "Python Cookbook" 2nd ed. Also, natürlich habe ich einen unglaublichen Sweet Spot für diesen speziellen Python-Fehler ... ;-).

Answer 2

Sie können friendList.append (self) in die Zeile vor dem if verschieben - Sie benötigen es in beiden Fällen. Sie müssen das Ergebnis auch nicht der Friendlist zuweisen - es ist ein Bug.

In Ihrem Algorithmus werden Sie wahrscheinlich dieselben Personen zweimal hinzufügen - wenn A ein Freund von B ist und B ein Freund von A. Sie müssen also eine Gruppe von Freunden behalten, die Sie bereits verarbeitet haben. Überprüfen Sie vor der Verarbeitung dieses Set und tun Sie nichts, wenn die Person bereits verarbeitet wurde.

Answer 3

Ist Ihre Identität korrekt?Der Hauptteil der Methode sollte relativ zu ihrer Definition eingerückt sein

Answer 4

Es gibt keine return Erklärung in der else Klausel. Wenn also degree != 0 zurückgegeben wird, gibt diese Methode immer None zurück. Sie möchten das Ergebnis jedes rekursiven Aufrufs getFriends an Ihre friendList anhängen und dann friendList zurückgeben.

Übrigens, wenn Sie diesen Algorithmus schneller machen möchten, gibt es gut etablierte Methoden, um dies entweder mit Graph-Algorithmen oder Matrix-Manipulation zu tun. Wenn Sie beispielsweise Freundschaftsbeziehungen mit einer Adjazenzmatrix A darstellen und alle Personen finden möchten, die sich innerhalb von n Grad der Trennung voneinander befinden, können Sie B=A^n berechnen. Wenn B[i][j] > 0, dann i und j sind innerhalb n Grad der Trennung voneinander. Matrix-Multiplikation ist einfach mit einem Paket wie NumPy.

Answer 5

(Leider kann ich nicht kommentieren Alex Antwort ... noch)

Ich weiß nicht wirklich wie die Idee, dass GetFriends einen Wert zurückgibt, die nie verwendet wird. Es funktioniert zwar, aber es sieht ein bisschen faszinierend aus;) Auch der erste Aufruf von getFriends wäre self.getFriends (degree, []) was verwirrend ist: wenn du eine Liste von Freunden bekommst, warum würdest du als eine gehen Argument eine leere Liste, oder?

Aus Gründen der Klarheit, denke ich, dass ich diese etwas andere Version bevorzugen, die Funktion _getFriends Helfer mit:

def getFriends(self, degree): 
    friendList = [] 
    self._getFriends(degree, friendList) 
    return friendList 

def _getFriends(self, degree, friendList): 
    friendList.append(self) 
    if degree: 
     for friend in self.friends: 
      friend._getFriends(degree-1, friendList)