Obtener amigos dentro de un grado de separación especificado

Question

todos. Soy un programador muy, muy nuevo. Mi lenguaje de elección en este momento es Python, y siento que tengo una sensación decente. Estoy empezando a aprender sobre recursividad. (Por cierto, si alguien puede recomendar una buena guía sobre esto, ¡por favor hágamelo saber!) Para que todos sepan, esta pregunta es muy elemental, y el código que estoy publicando es horrible, terriblemente incorrecto.

De todos modos, estoy tratando de escribir una función que obtenga todos los amigos dentro de un grado específico. Si lo paso 0 como título, solo me quiero a mí mismo. Si lo paso 1, me quiero a mí y a todos mis amigos. 2, me quiero a mí, a mis amigos y a todos sus amigos, y así sucesivamente.

He intentado varias formas diferentes de hacer esto, pero ninguno funciona. Intento visualizar cómo debería funcionar en teoría, y tampoco puedo entenderlo porque soy muy inexperto en esta área. Tal vez un alma amable aquí puede mostrarme todas las formas en que este código falla y luego explicar cómo hacerlo correctamente y/o recomendar una buena guía sobre el tema. Aquí va:

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) 

No funciona, y sé que he hecho cosas estúpidas y estúpidas. ¡Alguien por favor dame una bofetada y apúntame en la dirección correcta!

Gracias.

Answer 1

friendList = friendList.append(self) 

Esto establece friendList-None, sin condiciones, ya que es el valor de retorno invariable del método de cualquier lista append - así, fijar que rareza primera ... -!)

Una vez que haya arreglado eso, usted todavía necesita fijar la función para que siempre termine con return de algo - "caerse del extremo" devuelve None. Por ejemplo:

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 

que pueden y deben ser claramente rediseñado para eliminar la duplicación (SECO, no repita usted mismo, es el corazón de la programación ...):

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

PD: que (el problema alist=alist.append(...)) precisamente cómo volví a estar en contacto con mi esposa Anna en 2002 (hacía muchos años que no habíamos sido muy amables, pero nos perdimos de vista) comenzó a estudiar Python, utilizó exactamente esta construcción errónea, no podía entender por qué falló - miré alrededor de la comunidad de Python, vi y reconocí mi nombre , me envió un correo preguntándome sobre ello ... menos de dos años después estábamos casados, y poco después ella fue la primera mujer miembro de la Python Software Foundation y mi coautora en "Python Cookbook" 2nd ed. Entonces, por supuesto, tengo un punto dulce increíble para este error específico de Python ... ;-).

Answer 2

Puede mover friendList.append (self) a la línea anterior a if - lo necesita en ambos casos. Tampoco necesita asignar el resultado a la lista de amigos, es un error.

En su algoritmo, es probable que agregue las mismas personas dos veces, si A es amigo de B y B es amigo de A. Por lo tanto, debe conservar un grupo de amigos que ya haya procesado. Antes del procesamiento, verifique este conjunto y no haga nada si la persona ya ha sido procesada.

Answer 3

¿Su identación es correcta?El cuerpo del método debe sangrarse en relación con su definición

Answer 4

No hay ninguna declaración return en la cláusula else. Entonces, si degree != 0, este método siempre devolverá None. Desea anexar el resultado de cada llamada recursiva getFriends a su friendList, y luego devolver friendList.

Por cierto, si desea que este algoritmo sea más rápido, existen métodos bien establecidos para hacerlo con algoritmos de gráfico o manipulación de matrices. Por ejemplo, si representa relaciones de amistad con una matriz de adyacencia A, y desea buscar a todas las personas que están dentro de los n grados de separación entre sí, puede calcular B=A^n. Si B[i][j] > 0, entonces i y j están dentro de n grados de separación entre sí. La multiplicación de matrices es fácil con un paquete como NumPy.

Answer 5

(Lo siento, no puedo comentar sobre la respuesta de Alex ... todavía)

que no me gusta mucho la idea de que GetFriends devuelve un valor que no se usa nunca. Funciona, seguro, pero parece un poco intrigante;) Además, la primera llamada a getFriends sería self.getFriends (grado, []) que es confuso: al obtener una lista de amigos, ¿por qué pasaría como un argumento una lista vacía, ¿verdad?

Para mayor claridad, creo que preferiría esta versión ligeramente diferente, utilizando la función auxiliar _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)