python3 - Obtener amigos dentro de un grado específico de separación

recursive loop python

Question

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

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

Answer 2

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

Realmente no me gusta la idea de que getFriends devuelva un valor que nunca se usa. 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ías como argumento? una lista vacía, ¿verdad?

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

Answer 3

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

Por cierto, si desea que este algoritmo sea más rápido, existen métodos bien establecidos para hacerlo con algoritmos de gráficos o con la manipulación de la matriz. Por ejemplo, si representa las relaciones de amistad con una matriz de adyacencia A , y desea encontrar a todas las personas que están dentro de 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 el uno del otro. La multiplicación de matrices es fácil con un paquete como NumPy .

Answer 4

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. Entonces, debe mantener 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 5

friendList = friendList.append(self)

Esto establece friendList en None , incondicionalmente, ya que ese es el valor de retorno invariable del método de friendList de cualquier lista, así que, primero corrige esa rareza ...! -)

Una vez que haya solucionado eso, aún necesita corregir la función para que siempre termine con el return de algo: "caerse del extremo" devuelve None . P.ej:

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 puede y debe ser refactorizado para eliminar la duplicación (DRY, Do not Repeat Yourself, 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: ese (el problema alist=alist.append(...) ) precisamente cómo volví a estar en contacto con mi esposa Anna en 2002 (no habíamos sido muy amables muchos años antes, pero habíamos perdido la pista de cada uno otro) - 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, vio y reconoció mi nombre, me envió un correo preguntándome sobre ello ... menos de dos años después Estuve casado, 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 ... ;-).