Menu
I need a kick in the head on this one. I have the following recursive function defined:
def perms(s):
if(len(s)==1):
return s
res = ''
for x in xrange(len(s)):
res += s[x] + perms(s[0:x] + s[x+1:len(s)])
return res + '\n'
perms("abc") currently returns:
abccb
bacca
cabba
The desired result is
abc
acd
bac
bca
cab
cba
Where am I going wrong here? How can I think about this differently to come up with the solution?
Note: I am aware of the itertools function. I am trying to understand how to implement permutations recursively for my own learning. That is why I would prefer someone to point out what is wrong with my code, and how to think differently to solve it. Thanks!
943
To find all possible permutations of a given string, you can use the itertools module which has a useful method called permutations(iterable[, r]). This method return successive r length permutations of elements in the iterable as tuples.
Method 1(Using Recursion) :Create a recursive function say permute(string s, int l, int r), and pass string along with starting index of the string and the ending index of the string. Base condition will be if(l==r) then print the s. Otherwise, run a loop from [l, r] And, swap(s[l], s[i])
A. To create combinations without using itertools, iterate the list one by one and fix the first element of the list and make combinations with the remaining list. Similarly, iterate with all the list elements one by one by recursion of the remaining list.
Python also accepts function recursion, which means a defined function can call itself. Recursion is a common mathematical and programming concept. It means that a function calls itself. This has the benefit of meaning that you can loop through data to reach a result.
The result of permutations will be a collection, let's say a list. It will make your code cleaner if you think this way and if required you can join the results into a single string. A simple example will be
def perms(s):
if(len(s)==1): return [s]
result=[]
for i,v in enumerate(s):
result += [v+p for p in perms(s[:i]+s[i+1:])]
return result
perms('abc')
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
print('\n'.join(perms('abc')))
abc
acb
bac
bca
cab
cba
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
