Building Permutation with Python

Question

I'm trying to write a programme to get all permutations of a string of letter using recursion. As I'm a beginner in Python, I learnt about recursion with examples like Fibonacci Number and Factorial. I understand these math examples, but I still struggle with building a functional programme with recursion. I tried to understand other similar issues on web but still cannot grasp the concept.

So the problem is: How to get all permutations of a string of letter? For example str='abc' . My logic goes something like this:

1. create 3 slots for 3 letters abc
2. add in a letter, say 'a', and it can go to all 3 slots
3. building on the previous case, put in 'b'. Now only 2 slots left, and b can go to any of the 2 slot.
4. repeat until no more slot left. Now we reach a base case where no. of slot = 0.

But I cannot write in code

Answer 1

I have implemented your algorithm in python, using a string containing dots '.' as the slots. Of course this means the algorithm won't work if you also have dots in the original string.

I have blanked out most of the lines of my implementation; it's up to you to finish it. Before blanking out those lines, I tested it, and it works.

• create 3 slots for 3 letters abc: '.' * len(s)
• add in a letter, say 'a', and it can go to all 3 slots: use function insert in a for-loop where i is the position of every '.' in slots
• building on the previous case, put in 'b'. Now only 2 slots left, and b can go to any of the 2 slot: after every insert, make a recursive call
• repeat until no more slot left. Now we reach a base case where no. of slot = 0

def permutations(s):
    return helper_perms(s, '.' * len(s), len(s))

def helper_perms(s, slots, k):
    if ??? # base case
        return ???
    else:
        results = []
        for i,c in enumerate(slots):
            if c == '.':
                results.extend(helper_perms(s, ???, ???)) # insert some char from s into slots and make a recursive call
        return results

def insert(slots, i, c):
    return ??? # return a new string with character c inserted at position i in slots

print( permutations('abc') )
# ['cba', 'cab', 'bca', 'acb', 'bac', 'abc']

Answer 2

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 = ("","","","")
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, ('', '', '', '')