Atascado/a con la implementación de permutaciones utilizando recursión. No obtengo ninguna salida.

01 Aug, 2023 Programación 0

Quiero escribir una función permutations(route, cities). Debe tomar una lista (cities), agregar todas las permutaciones posibles de las cities a la lista route e imprimir cada permutación en una nueva línea de la route. Cada permutación debe comenzar con la primera ciudad, es decir, “Boston”.

Estoy usando la recursividad para esta implementación, pero no logro que funcione.

def permutations(route, cities):

    def recurs(cities_temp):

        if len(cities_temp) == 0:
            return []
        elif len(cities_temp) == 1:
            return [cities_temp]
        else:
            route_temp = []

            for i in range(len(cities_temp)):
                x = cities_temp[i] #x es el elemento i de la lista de entrada
                y = cities_temp[:i] + cities_temp[1+i:] #y es lo que queda (todo excepto el elemento i)

                for j in recurs(y):
                    route_temp.append([x] + j)
            return route_temp

    route = recurs(cities)

    print(' '.join([city_names[i] for i in route]))

city_names = ["Boston", "Seattle", "Chicago", "Dallas"]

permutations([0], list(range(1, len(city_names)))) #llamando a la función permutations

¿Podrían echarle un vistazo y decirme qué estoy haciendo mal?

davy.ai

August 1, 2023 at 12:21 pm

Parece que el problema principal con la implementación actual es que la lista route no se actualiza a medida que se generan las permutaciones. En su lugar, se crea una nueva lista route_temp dentro de la función recurs y se devuelve como resultado final. Esto significa que la lista route pasada como argumento a la función permutations no cambia.

Para solucionar este problema, una posible solución sería modificar la función recurs para que tome la lista route como un argumento adicional y la actualice a medida que se generen las permutaciones. A continuación, se muestra una implementación actualizada:

def permutations(route, cities):

    def recurs(route, cities_temp):

        if len(cities_temp) == 0:
            return
        elif len(cities_temp) == 1:
            route.append(cities_temp[0])
            print(' '.join([city_names[i] for i in route]))
            route.pop()
        else:
            for i in range(len(cities_temp)):
                x = cities_temp[i] # x es el elemento i en la lista de entrada
                y = cities_temp[:i] + cities_temp[1+i:] # y son los elementos restantes (todo excepto el elemento i)

                route.append(x)
                recurs(route, y)
                route.pop()

    recurs(route, cities)

city_names = ["Boston", "Seattle", "Chicago", "Dallas"]
permutations([0], list(range(1, len(city_names))))

En esta implementación actualizada, la función recurs ahora recibe un argumento adicional route, que es la permutación actual que se está generando. La función primero verifica los casos base de una lista de entrada vacía o con un solo elemento, agregando la última ciudad a la lista route y imprimiéndola si se alcanza el primer caso.

Para listas de entrada más grandes, la función itera sobre cada elemento, agregándolo a route y llamando de forma recursiva a recurs en los elementos restantes (y). Después de cada llamada recursiva, se elimina el elemento agregado de route para prepararse para la siguiente iteración.

La función principal permutations ahora llama a recurs con los argumentos route y cities iniciales, asegurando que la lista route se actualice con todas las permutaciones generadas. Finalmente, la función imprime cada permutación en la lista route formateada con los nombres de ciudad correspondientes en la lista city_names.

Answer

davy.ai

August 1, 2023 at 12:21 pm
Parece que el problema principal con la implementación actual es que la lista route no se actualiza a medida que se generan las permutaciones. En su lugar, se crea una nueva lista route_temp dentro de la función recurs y se devuelve como resultado final. Esto significa que la lista route pasada como argumento a la función permutations no cambia.

Para solucionar este problema, una posible solución sería modificar la función recurs para que tome la lista route como un argumento adicional y la actualice a medida que se generen las permutaciones. A continuación, se muestra una implementación actualizada:
```
def permutations(route, cities):

    def recurs(route, cities_temp):

        if len(cities_temp) == 0:
            return
        elif len(cities_temp) == 1:
            route.append(cities_temp[0])
            print(' '.join([city_names[i] for i in route]))
            route.pop()
        else:
            for i in range(len(cities_temp)):
                x = cities_temp[i] # x es el elemento i en la lista de entrada
                y = cities_temp[:i] + cities_temp[1+i:] # y son los elementos restantes (todo excepto el elemento i)

                route.append(x)
                recurs(route, y)
                route.pop()

    recurs(route, cities)

city_names = ["Boston", "Seattle", "Chicago", "Dallas"]
permutations([0], list(range(1, len(city_names))))
```
En esta implementación actualizada, la función recurs ahora recibe un argumento adicional route, que es la permutación actual que se está generando. La función primero verifica los casos base de una lista de entrada vacía o con un solo elemento, agregando la última ciudad a la lista route y imprimiéndola si se alcanza el primer caso.

Para listas de entrada más grandes, la función itera sobre cada elemento, agregándolo a route y llamando de forma recursiva a recurs en los elementos restantes (y). Después de cada llamada recursiva, se elimina el elemento agregado de route para prepararse para la siguiente iteración.

La función principal permutations ahora llama a recurs con los argumentos route y cities iniciales, asegurando que la lista route se actualice con todas las permutaciones generadas. Finalmente, la función imprime cada permutación en la lista route formateada con los nombres de ciudad correspondientes en la lista city_names.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Atascado/a con la implementación de permutaciones utilizando recursión. No obtengo ninguna salida.

Answer

davy.ai