Stuck with implementing permutations using recursion. Not getting any output-CodePudding

I want to write a function permutations(route, cities). It should take a list (cities), append every possible permutations of the cities to the route list, and print each permutation in route on a new line. Every permutation must start with the first city, i.e. "Boston".

I am using recursion for this implementation, but can't get it to work.

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 is item i in the input list
                y = cities_temp[:i]   cities_temp[1 i:] #y is the remaining (everything but item 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)))) #calling the permutations function

Can you all please take a look at it and let me know what I am doing wrong?

CodePudding user response：

I don't know what's wrong with the code in your question, but think you're "reinventing-the-wheel" since you can make use of the itertools.permutations() function to get them:

from itertools import permutations
from pprint import pprint

city_names = ["Boston", "Seattle", "Chicago", "Dallas"]
permutes = [(city_names[0],) p for p in permutations(city_names[1:])]
pprint(permutes)

Output:

[('Boston', 'Seattle', 'Chicago', 'Dallas'),
 ('Boston', 'Seattle', 'Dallas', 'Chicago'),
 ('Boston', 'Chicago', 'Seattle', 'Dallas'),
 ('Boston', 'Chicago', 'Dallas', 'Seattle'),
 ('Boston', 'Dallas', 'Seattle', 'Chicago'),
 ('Boston', 'Dallas', 'Chicago', 'Seattle')]

CodePudding user response：

The problem was with mapping the permuted index with the city name..I've edited the code using map function. Have a look.

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 is item i in the input list
                y = cities_temp[:i]   cities_temp[1 i:] #y is the remaining (everything but item I)

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

    route = recurs(cities)

    # mapping index with city names from city_names list
    mapped_route = [list(map(lambda x : city_names[x],r)) for r in route]

    # adding boston in front of every permutation
    final_route = list(map(lambda x : "Boston " x,[' '.join(r) for r in mapped_route]))

    print(final_route)


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

permutations([0], list(range(1, len(city_names))))