Home > front end >  permutations with recursion in python
permutations with recursion in python

Time:09-10

I have a task to make a code that takes a list of undefined number and print all permutations with the first constant using recursion and here is a code I wrote but I don't know where is the problem

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


def permutations(route, ports):
    for items in ports:
        route.append(ports)
        ports = ports[:items] ports[items 1:]
        permutations(route, ports)
    print(' '.join([portnames[i] for i in route]))


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

note: the function must contain

CodePudding user response:

You can user the itertools module for this.

Basically, when doing permutations and combinations, this is a very useful place.


import itertools

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


x = itertools.permutations(portnames)
y = list(x)

# or this is you want to inspect the loop
# y = []
# for i in x:
#     y.append(i)

y

The result is a big list:

[('PAN', 'AMS', 'CAS', 'NYC', 'HEL')
('PAN', 'AMS', 'CAS', 'HEL', 'NYC')
('PAN', 'AMS', 'NYC', 'CAS', 'HEL')
('PAN', 'AMS', 'NYC', 'HEL', 'CAS')
('PAN', 'AMS', 'HEL', 'CAS', 'NYC')
('PAN', 'AMS', 'HEL', 'NYC', 'CAS')
('PAN', 'CAS', 'AMS', 'NYC', 'HEL')
('PAN', 'CAS', 'AMS', 'HEL', 'NYC')
('PAN', 'CAS', 'NYC', 'AMS', 'HEL')
('PAN', 'CAS', 'NYC', 'HEL', 'AMS')
('PAN', 'CAS', 'HEL', 'AMS', 'NYC')
('PAN', 'CAS', 'HEL', 'NYC', 'AMS')
('PAN', 'NYC', 'AMS', 'CAS', 'HEL')
('PAN', 'NYC', 'AMS', 'HEL', 'CAS')
('PAN', 'NYC', 'CAS', 'AMS', 'HEL')
('PAN', 'NYC', 'CAS', 'HEL', 'AMS')
('PAN', 'NYC', 'HEL', 'AMS', 'CAS')
('PAN', 'NYC', 'HEL', 'CAS', 'AMS')
('PAN', 'HEL', 'AMS', 'CAS', 'NYC')
('PAN', 'HEL', 'AMS', 'NYC', 'CAS')
('PAN', 'HEL', 'CAS', 'AMS', 'NYC')
('PAN', 'HEL', 'CAS', 'NYC', 'AMS')
...
..and so on

('HEL', 'NYC', 'PAN', 'CAS', 'AMS'),
 ('HEL', 'NYC', 'AMS', 'PAN', 'CAS'),
 ('HEL', 'NYC', 'AMS', 'CAS', 'PAN'),
 ('HEL', 'NYC', 'CAS', 'PAN', 'AMS'),
 ('HEL', 'NYC', 'CAS', 'AMS', 'PAN')]

As a side note, whilst your attempt was good, because the output is large and the number of recursions is large, you could get stack overflow.

There were two alternative things that you can do:

  • increase the limit of recursions
  • transform to a while or for loop.

However, the itertool.permutations option is most suitable.

CodePudding user response:

We can write permutations(t) of any iterable t using inductive reasoning -

  1. if t is empty, yield the empty permutation, ()
  2. (inductive) t has at least one element. For all p of the recursive sub-problem permutations(t[1:]), for all i of inserts(p, t[0]), yield i
def permutations(t):
  if not t:
    yield ()                       # 1. empty t
  else:
    for p in permutations(t[1:]):  # 2. at least one element
      for i in inserts(p, t[0]):
        yield i

Where inserts(t, x) can be written using inductive reasoning as well -

  1. If the input t is empty, yield the final insert, (x)
  2. (inductive) t has at least one element. yield x prepended to t and for all i of the recursive sub-problem inserts(t[1:], x) yield t[0] prepended to i
def inserts(t, x):
  if not t:
    yield (x,)                       # 1. empty t
  else:
    yield (x, *t)                    # 2. at least one element
    for i in inserts(t[1:], x):
      yield (t[0], *i)
t = ("           
  • Related