Stuck with implementing permutations using recursion. Not getting any output

Question

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?

What's the point of the route argument to permutations? It seems redundant. — MisterMiyagi
– MisterMiyagi, Commented Jan 3, 2022 at 13:45
"but can't get it to work." What exactly does that mean? The title implies you get no output at all. Running the code loudly fails with TypeError: list indices must be integers or slices, not list, though. — MisterMiyagi
– MisterMiyagi, Commented Jan 3, 2022 at 13:47
I didn't look in detail, but I'm guessing if len(cities_temp) == 0: return [] elif len(cities_temp) == 1: return [cities_temp] should instead be if len(cities_temp) <= 1: return [cities_temp]. — Stef
– Stef, Commented Jan 3, 2022 at 13:47
Removing everything from route = ... to ... in route])) and replacing it with print(' '.join(city_names[i] for routes in recurs(cities) for i in route + routes)) should "work", for a given definition of "work". — MisterMiyagi
– MisterMiyagi, Commented Jan 3, 2022 at 13:53
Also, why do you pass list(range(1, len(city_names))) and not directly city_names? Also note that range(1, len(city_names)) has one fewer element than city_names. You probably want either range(len(city_names)) or range(1, len(city_names)+1). — Stef
– Stef, Commented Jan 3, 2022 at 13:54

martineau · Accepted Answer · 2022-01-04 21:07:26Z

2

I don't know what's wrong with the code in your question, but it sounds like you may be reinventing the wheel since you can make use of the itertools.permutations() function in the standard library to get them:

from itertools import permutations
from pprint import pprint

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

first, *rest = city_names  # Unpack.
routes = [(first, *permutation) for permutation in permutations(rest)]
pprint(routes)

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')]

If you don't want or can't use itertools and you want or have to do it recursively, you first have to find out how that would work. In this case that would be something like this pseudo-code:

permutations[a, b, c, ...] = [
    a + permutations[b, c, ...], b + permutations[a, c, ..], ..., 
]
with the final term being:
    permutations[a] = [a]

Here's how to implement that in Python:

from pprint import pprint

def permutations(s):
    if len(s) <= 1:
        return [s]
    else:
        perms = []

    for e in permutations(s[:-1]):
        for i in range(len(e) + 1):
            perms.append(e[:i] + s[-1:] + e[i:])

    return perms


city_names = ["Boston", "Seattle", "Chicago", "Dallas"]
first, *rest = city_names  # Unpack.
routes = [(first, *permutation) for permutation in permutations(rest)]
pprint(routes)

edited Jan 4, 2022 at 21:07

answered Jan 3, 2022 at 17:42

martineau

124k29 gold badges181 silver badges319 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

idioteque11 Over a year ago

Thanks for linking the permutations() documentation. I have been looking for it everywhere. It's good to see the algorithm. This is actually for an assignment, that's why use of itertools is discouraged.

martineau Over a year ago

Note that the sample implementation shown in the documentation isn't recursive — is that a requirement?

idioteque11 · Accepted Answer · 2022-01-16 09:31:28Z

I had ignored this exercise until I am in a better mindset but finally was able to solve it just like the instructor wished.

Here is the code. Thanks for all the responses to my original question.

portnames = ["PAN", "AMS", "CAS", "NYC", "HEL"]

def permutations(route, ports):
    n = len(ports) - 1

    def recursion(ports):
        if len(ports) == 1:
            return [ports]
        else:
            lst = []

            for i in range(len(ports)):
                x = [ports[i]]
                xs = ports[:i] + ports[i+1:]

                for j in recursion(xs):
                    if len(j) == n:
                        lst.append(route + x + j)
                    else:
                        lst.append(x + j)
        
        return lst
    

    for p in recursion(list(range(1, len(portnames)))):
        print(' '.join([portnames[i] for i in p]))
                    
 
    return recursion(ports)

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

Collectives™ on Stack Overflow

Stuck with implementing permutations using recursion. Not getting any output

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related