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 ... ;-).