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
orfor
loop.
However, the itertool.permutations
option is most suitable.
CodePudding user response:
We can write permutations(t)
of any iterable t
using inductive reasoning -
- if
t
is empty, yield the empty permutation,()
- (inductive)
t
has at least one element. For allp
of the recursive sub-problempermutations(t[1:])
, for alli
ofinserts(p, t[0])
, yieldi
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 -
- If the input
t
is empty, yield the final insert,(x)
- (inductive)
t
has at least one element. yieldx
prepended tot
and for alli
of the recursive sub-probleminserts(t[1:], x)
yieldt[0]
prepended toi
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 = ("