特定の分離度の友人を取得する

Question

すべて。私は非常に新しいプログラマーです。現時点で私が選んでいる言語はPythonであり、私はそれに対してまともな気持ちがあるように感じます。私はちょうど再帰について学び始めています。 （ちなみに、誰かがこれについての良いガイドをお勧めすることができれば、私に教えてください！）あなたが知っているように、この質問は非常に初歩的で、私が投稿しているコードはひどくひどく間違っています。

とにかく、私は指定された程度のすべての友人を取得する関数を書こうとしています。私が度として0を渡すならば、私は自分自身が欲しいだけです。私がそれを渡すと、私と私のすべての友達が欲しいです。 2、私は、私の友人、そして彼らのすべての友達、などをしたい。

私はこれを行うにはかなりの異なる方法を試しましたが、何もしませんでした。私はそれが理論的にどのように機能すべきかを視覚化しようとしています。私はこの分野では経験の浅いのでどちらかといえます。おそらくここで親切な魂は、このコードが失敗するすべての方法を私に示すことができますし、適切にそれを行う方法を説明し、そして/または主題の良いガイドをお勧めします。ここに行く：

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

それが動作しない、と私は愚かな、愚かなことをやった知っています。誰かが私を叩き、正しい方向に私を指差してください！

ありがとうございました。

Answer 1

friendList = friendList.append(self) 

これは、それが任意のリストのappend方法の不変の戻り値だとして、無条件に、NoneからfriendListを設定します - ので、最初そのすごみ...修正 - あなたはたら）

を！それでも、あなたはまだ何かのreturnで終わるように関数を修正する必要があることを修正 - "最後に落ちる"はNoneを返します。例：

と明確に（...、DRY自分を繰り返してはいけない、プログラミングの心臓部である）重複を排除するためにリファクタリングする必要がありますすることができ

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 

：

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

PS：その（ alist=alist.append(...)号）正確には私は2002年に妻のアンナと連絡を取った（私たちは何年も前に恋人ではなかったが、お互いを見失っていた） - 彼女はPythonを学び始め、この誤った構造は、なぜ失敗したのか理解できませんでした - Pythonコミュニティを見て、私の名前を見て認識しました2年も経たずに私たちは結婚しました。すぐに彼女はPython Software Foundationの最初の女性メンバーであり、「Python Cookbook」第2版の共著者でした。だからもちろん、私はこの特定のPythonエラーのために素晴らしいスイートスポットを持っています... ;-)。

Answer 2

あなたはfriendList.append（self）をifの前の行に移動できます。どちらの場合でもfriendList.append（self）を必要とします。結果をフレンドリストに割り当てる必要もありません。バグです。

あなたのアルゴリズムでは、AがBの友人であり、BがAの友人である場合、同じ人を2度追加する可能性が高いです。あなたは既に処理した友人のセットを保持する必要があります。処理する前にこのセットをチェックし、その人が既に処理されている場合は何もしないでください。

Answer 3

あなたの表記は正しいですか？メソッド本体がその定義に対して字下げされている必要があります

Answer 4

else節にはreturnの文はありません。したがって、degree != 0の場合、このメソッドは常にNoneを返します。各再帰呼び出しの結果をfriendListに追加してからfriendListを返します。

ところで、このアルゴリズムをより高速にしたい場合は、グラフアルゴリズムまたはマトリックス操作でこれを行う方法が確立されています。たとえば、隣接関係行列Aで友情関係を表し、お互いがn度以内のすべての人物を検索する場合は、B=A^nを計算できます。 B[i][j] > 0の場合、iとjは、それぞれn以内にあります。行列乗算はNumPyのようなパッケージで簡単です。

Answer 5

（申し訳ありませんが、私はアレックスの答えにコメントすることはできません... まだ）

私は本当にgetFriendsが使用されることはありません値を返すという考えが好きではありません。それはちょっと面白く見えますが、ちょっと興味があります） また、getFriendsの最初の呼び出しはself.getFriends（degree、[]）です。これは混乱しています。引数は空リストですよね？明確にするために

、私は_getFriendsヘルパー関数を使用して、このわずかに異なるバージョンを好むだろうと思う：

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)