Reputation: 3
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
Upvotes: 0
Views: 476
Reputation: 135415
We can write permutations(t)
of any iterable t
using inductive reasoning -
t
is empty, yield the empty permutation, ()
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 -
t
is empty, yield the final insert, (x)
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 = ("🔴","🟢","🔵","🟡")
for p in permutations(t):
print("".join(p))
🔴🟢🔵🟡
🟢🔴🔵🟡
🟢🔵🔴🟡
🟢🔵🟡🔴
🔴🔵🟢🟡
🔵🔴🟢🟡
🔵🟢🔴🟡
🔵🟢🟡🔴
🔴🔵🟡🟢
🔵🔴🟡🟢
🔵🟡🔴🟢
🔵🟡🟢🔴
🔴🟢🟡🔵
🟢🔴🟡🔵
🟢🟡🔴🔵
🟢🟡🔵🔴
🔴🟡🟢🔵
🟡🔴🟢🔵
🟡🟢🔴🔵
🟡🟢🔵🔴
🔴🟡🔵🟢
🟡🔴🔵🟢
🟡🔵🔴🟢
🟡🔵🟢🔴
Python has strong support for generators and offers delegation using yield from ..
. We can simplify the above definitions while maintaining the exact same behaviour -
def permutations(t):
if not t:
yield ()
else:
for p in permutations(t[1:]):
yield from inserts(p, t[0]) # <-
def inserts(t, x):
if not t:
yield (x,)
else:
yield (x, *t)
yield from map(lambda r: (t[0], *r), inserts(t[1:], x)) # <-
Generators are a good fit for combinatorics because working with them is natural and straightforward -
# find all permutations where red is left of green
for p in permutations(t):
if p.index("🔴") < p.index("🟢"):
print("".join(p))
🔴🟢🔵🟡
🔴🔵🟢🟡
🔵🔴🟢🟡
🔴🔵🟡🟢
🔵🔴🟡🟢
🔵🟡🔴🟢
🔴🟢🟡🔵
🔴🟡🟢🔵
🟡🔴🟢🔵
🔴🟡🔵🟢
🟡🔴🔵🟢
🟡🔵🔴🟢
# find all permutations where blue and yellow are adjacent
for p in permutations(t):
if abs(p.index("🔵") - p.index("🟡")) == 1:
print("".join(p))
🔴🟢🔵🟡
🟢🔴🔵🟡
🟢🔵🟡🔴
🔴🔵🟡🟢
🔵🟡🔴🟢
🔵🟡🟢🔴
🔴🟢🟡🔵
🟢🔴🟡🔵
🟢🟡🔵🔴
🔴🟡🔵🟢
🟡🔵🔴🟢
🟡🔵🟢🔴
Additionally generators can be paused/stopped at any time, allowing us to skip potentially millions of computations for significantly large problems -
# which permutation is in rainbow order?
for (n, p) in enumerate(permutations(t)):
if p == ("🔴", "🟡", "🟢", "🔵"):
print(f"permutation {n} is in rainbow order, {p}")
break # <- stops generating additional permutations
permutation 16 is in rainbow order, ('🔴', '🟡', '🟢', '🔵')
We use permutations
with your portnames
data now -
portnames = ["PAN", "AMS", "CAS", "NYC", "HEL"]
for x in permutations(portnames):
print(x)
('PAN', 'AMS', 'CAS', 'NYC', 'HEL')
('AMS', 'PAN', 'CAS', 'NYC', 'HEL')
('AMS', 'CAS', 'PAN', 'NYC', 'HEL')
('AMS', 'CAS', 'NYC', 'PAN', 'HEL')
('AMS', 'CAS', 'NYC', 'HEL', 'PAN')
('PAN', 'CAS', 'AMS', 'NYC', 'HEL')
('CAS', 'PAN', 'AMS', 'NYC', 'HEL')
('CAS', 'AMS', 'PAN', 'NYC', 'HEL')
('CAS', 'AMS', 'NYC', 'PAN', 'HEL')
('CAS', 'AMS', 'NYC', 'HEL', 'PAN')
('PAN', 'CAS', 'NYC', 'AMS', 'HEL')
('CAS', 'PAN', 'NYC', 'AMS', 'HEL')
('CAS', 'NYC', 'PAN', 'AMS', 'HEL')
('CAS', 'NYC', 'AMS', 'PAN', 'HEL')
('CAS', 'NYC', 'AMS', 'HEL', 'PAN')
('PAN', 'CAS', 'NYC', 'HEL', 'AMS')
('CAS', 'PAN', 'NYC', 'HEL', 'AMS')
('CAS', 'NYC', 'PAN', 'HEL', 'AMS')
('CAS', 'NYC', 'HEL', 'PAN', 'AMS')
('CAS', 'NYC', 'HEL', 'AMS', 'PAN')
('PAN', 'AMS', 'NYC', 'CAS', 'HEL')
('AMS', 'PAN', 'NYC', 'CAS', 'HEL')
('AMS', 'NYC', 'PAN', 'CAS', 'HEL')
('AMS', 'NYC', 'CAS', 'PAN', 'HEL')
('AMS', 'NYC', 'CAS', 'HEL', 'PAN')
('PAN', 'NYC', 'AMS', 'CAS', 'HEL')
('NYC', 'PAN', 'AMS', 'CAS', 'HEL')
('NYC', 'AMS', 'PAN', 'CAS', 'HEL')
('NYC', 'AMS', 'CAS', 'PAN', 'HEL')
('NYC', 'AMS', 'CAS', 'HEL', 'PAN')
('PAN', 'NYC', 'CAS', 'AMS', 'HEL')
('NYC', 'PAN', 'CAS', 'AMS', 'HEL')
('NYC', 'CAS', 'PAN', 'AMS', 'HEL')
('NYC', 'CAS', 'AMS', 'PAN', 'HEL')
('NYC', 'CAS', 'AMS', 'HEL', 'PAN')
('PAN', 'NYC', 'CAS', 'HEL', 'AMS')
('NYC', 'PAN', 'CAS', 'HEL', 'AMS')
('NYC', 'CAS', 'PAN', 'HEL', 'AMS')
('NYC', 'CAS', 'HEL', 'PAN', 'AMS')
('NYC', 'CAS', 'HEL', 'AMS', 'PAN')
('PAN', 'AMS', 'NYC', 'HEL', 'CAS')
('AMS', 'PAN', 'NYC', 'HEL', 'CAS')
('AMS', 'NYC', 'PAN', 'HEL', 'CAS')
('AMS', 'NYC', 'HEL', 'PAN', 'CAS')
('AMS', 'NYC', 'HEL', 'CAS', 'PAN')
('PAN', 'NYC', 'AMS', 'HEL', 'CAS')
('NYC', 'PAN', 'AMS', 'HEL', 'CAS')
('NYC', 'AMS', 'PAN', 'HEL', 'CAS')
('NYC', 'AMS', 'HEL', 'PAN', 'CAS')
('NYC', 'AMS', 'HEL', 'CAS', 'PAN')
('PAN', 'NYC', 'HEL', 'AMS', 'CAS')
('NYC', 'PAN', 'HEL', 'AMS', 'CAS')
('NYC', 'HEL', 'PAN', 'AMS', 'CAS')
('NYC', 'HEL', 'AMS', 'PAN', 'CAS')
('NYC', 'HEL', 'AMS', 'CAS', 'PAN')
('PAN', 'NYC', 'HEL', 'CAS', 'AMS')
('NYC', 'PAN', 'HEL', 'CAS', 'AMS')
('NYC', 'HEL', 'PAN', 'CAS', 'AMS')
('NYC', 'HEL', 'CAS', 'PAN', 'AMS')
('NYC', 'HEL', 'CAS', 'AMS', 'PAN')
('PAN', 'AMS', 'CAS', 'HEL', 'NYC')
('AMS', 'PAN', 'CAS', 'HEL', 'NYC')
('AMS', 'CAS', 'PAN', 'HEL', 'NYC')
('AMS', 'CAS', 'HEL', 'PAN', 'NYC')
('AMS', 'CAS', 'HEL', 'NYC', 'PAN')
('PAN', 'CAS', 'AMS', 'HEL', 'NYC')
('CAS', 'PAN', 'AMS', 'HEL', 'NYC')
('CAS', 'AMS', 'PAN', 'HEL', 'NYC')
('CAS', 'AMS', 'HEL', 'PAN', 'NYC')
('CAS', 'AMS', 'HEL', 'NYC', 'PAN')
('PAN', 'CAS', 'HEL', 'AMS', 'NYC')
('CAS', 'PAN', 'HEL', 'AMS', 'NYC')
('CAS', 'HEL', 'PAN', 'AMS', 'NYC')
('CAS', 'HEL', 'AMS', 'PAN', 'NYC')
('CAS', 'HEL', 'AMS', 'NYC', 'PAN')
('PAN', 'CAS', 'HEL', 'NYC', 'AMS')
('CAS', 'PAN', 'HEL', 'NYC', 'AMS')
('CAS', 'HEL', 'PAN', 'NYC', 'AMS')
('CAS', 'HEL', 'NYC', 'PAN', 'AMS')
('CAS', 'HEL', 'NYC', 'AMS', 'PAN')
('PAN', 'AMS', 'HEL', 'CAS', 'NYC')
('AMS', 'PAN', 'HEL', 'CAS', 'NYC')
('AMS', 'HEL', 'PAN', 'CAS', 'NYC')
('AMS', 'HEL', 'CAS', 'PAN', 'NYC')
('AMS', 'HEL', 'CAS', 'NYC', 'PAN')
('PAN', 'HEL', 'AMS', 'CAS', 'NYC')
('HEL', 'PAN', 'AMS', 'CAS', 'NYC')
('HEL', 'AMS', 'PAN', 'CAS', 'NYC')
('HEL', 'AMS', 'CAS', 'PAN', 'NYC')
('HEL', 'AMS', 'CAS', 'NYC', 'PAN')
('PAN', 'HEL', 'CAS', 'AMS', 'NYC')
('HEL', 'PAN', 'CAS', 'AMS', 'NYC')
('HEL', 'CAS', 'PAN', 'AMS', 'NYC')
('HEL', 'CAS', 'AMS', 'PAN', 'NYC')
('HEL', 'CAS', 'AMS', 'NYC', 'PAN')
('PAN', 'HEL', 'CAS', 'NYC', 'AMS')
('HEL', 'PAN', 'CAS', 'NYC', 'AMS')
('HEL', 'CAS', 'PAN', 'NYC', 'AMS')
('HEL', 'CAS', 'NYC', 'PAN', 'AMS')
('HEL', 'CAS', 'NYC', 'AMS', 'PAN')
('PAN', 'AMS', 'HEL', 'NYC', 'CAS')
('AMS', 'PAN', 'HEL', 'NYC', 'CAS')
('AMS', 'HEL', 'PAN', 'NYC', 'CAS')
('AMS', 'HEL', 'NYC', 'PAN', 'CAS')
('AMS', 'HEL', 'NYC', 'CAS', 'PAN')
('PAN', 'HEL', 'AMS', 'NYC', 'CAS')
('HEL', 'PAN', 'AMS', 'NYC', 'CAS')
('HEL', 'AMS', 'PAN', 'NYC', 'CAS')
('HEL', 'AMS', 'NYC', 'PAN', 'CAS')
('HEL', 'AMS', 'NYC', 'CAS', 'PAN')
('PAN', 'HEL', 'NYC', 'AMS', 'CAS')
('HEL', 'PAN', 'NYC', 'AMS', 'CAS')
('HEL', 'NYC', 'PAN', 'AMS', 'CAS')
('HEL', 'NYC', 'AMS', 'PAN', 'CAS')
('HEL', 'NYC', 'AMS', 'CAS', 'PAN')
('PAN', 'HEL', 'NYC', 'CAS', 'AMS')
('HEL', 'PAN', 'NYC', 'CAS', 'AMS')
('HEL', 'NYC', 'PAN', 'CAS', 'AMS')
('HEL', 'NYC', 'CAS', 'PAN', 'AMS')
('HEL', 'NYC', 'CAS', 'AMS', 'PAN')
Upvotes: 2
Reputation: 5764
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:
while
or for
loop.However, the itertool.permutations
option is most suitable.
Upvotes: 0