In this forum members can discuss topics about specific programming languages.
6 posts • Page 1 of 1
Hi guys. i've recently learned python and am trying to cement the skills using the problems on this site. i am however unable to calculate permutations of given strings unless i know the number of elements and then it gets a bit messy. i was wondering if there is an easy way to do this which im missing?
Not knowing anything about Python, I nonetheless think that some recursive function on the length of the string should work. I.e., select one element of your string, put it in front and then permute the remaining characters, prepending the first character to each of the results.cheesetikka wrote:Hi guys. i've recently learned python and am trying to cement the skills using the problems on this site. i am however unable to calculate permutations of given strings unless i know the number of elements and then it gets a bit messy. i was wondering if there is an easy way to do this which im missing?
yeah ive sort of been trying to do that but cant work out quite how because each element needs to be placed at the front anf then something needs to be done to save it somewhere. this is the sort of thing i have tried to write, but i cant get my thoughts down properly and it is clearly wrong. i am having trouble with the interation step producing me a list rather than an individual list. i put this down to the for statement and think that it needs to be taken outside of the function deinition. i have however been on the computer all day and have got a bit of mid-afternoon mental block and am really struggling. could anyone provide a gently nudge. thanks again
for i in range(len(x)):
for i in range(len(x)):
With recursion it's important to think of the type of your input and output. To make things easy, let's make sure the functions thinks only in terms of lists. Hence the initial conversion. So, if we want the permutations of the list [1,2], what do we expect? The two permutations, themselves lists, all returned together as a list. [[1,2],[2,1]]. So the input of the function is a list, but the output is a list of lists, and it's crucial to always keep this in mind because the function is going to be supplying it's own input and using it's own output.
Code: Select all
def permute(s): s=list(s) if len(s)==1: return [s] out= for i in range(len(s)): first=s[i] #Pick out an element in the sequence to put at the beginning for smallerPerm in permute(s[:i]+s[i+1:]): #Permute the rest of the sequence without the element 'first' out.append([first]+smallerPerm) return out
Also essential in recursion is the stopping condition. In any recursive function definition I can think of, there should be an if statement dealing with the base case, in this case a singleton list that only has itself as a permutation. Since the parameter s is a list (if it wasn't originally, it now is), and the output has to be a list of lists, those extra square brackets are important. For example, permute() will return [], a nested list.
Since the input is a list and the output is a list of lists, we expect to have two levels of looping. The recursive step involves some slicing that might be confusing. To see what it means, try pasting the following into a shell:
I'm used to python 3, so you may need to tweak that.
Code: Select all
s=[0,1,2,3,4,5,6]; i=2; print s[:i] ; print s[i+1:]; print s[:i]+s[i+1:]
Again, note the importance of considering input and output. Since permute gives a list of lists, smallerPerm is a list. However, s is a list without nesting and so first is just an element, and we have to write [first] to concatenate it with smallerPerm. The result is a list, which we append (not extend) to out, as a single element. Therefore out is the list of lists.
When trying to understand recursion code or debug your own, a helpful tip is not to try and think what happens in the successive levels of recursion when the function calls itself. Assume that the function used inside the definition is correct and gives you what you want (make sure you know what that is, it's not always so easy) and see what should happen from there.