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:
- create 3 slots for 3 letters abc
- add in a letter, say 'a', and it can go to all 3 slots
- building on the previous case, put in 'b'. Now only 2 slots left, and b can go to any of the 2 slot.
- repeat until no more slot left. Now we reach a base case where no. of slot = 0.
But I cannot write in code
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 casereturn ???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 callreturn resultsdef insert(slots, i, c):return ??? # return a new string with character c inserted at position i in slotsprint( permutations('abc') )
# ['cba', 'cab', 'bca', 'acb', 'bac', 'abc']