python permutations

In this forum members can discuss topics about specific programming languages.
Post Reply
cheesetikka
Posts: 2
Joined: Mon Mar 21, 2011 4:47 pm

python permutations

Post by cheesetikka » Mon Mar 21, 2011 4:51 pm

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?

thanks :)

User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 9:43 am
Location: Netherlands

Re: python permutations

Post by Lord_Farin » Mon Mar 21, 2011 5:21 pm

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?

thanks :)
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.
Image

cheesetikka
Posts: 2
Joined: Mon Mar 21, 2011 4:47 pm

Re: python permutations

Post by cheesetikka » Mon Mar 21, 2011 5:39 pm

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

def permute(x,perm=[]):
lists=list(x)
for i in range(len(x)):
perm.append(lists)
permute(lists-lists,perm)
print perm

genious999
Posts: 54
Joined: Mon Oct 20, 2008 9:48 pm

Re: python permutations

Post by genious999 » Mon Mar 21, 2011 11:31 pm

Look in the itertools library, there is a function for permutations, and other similar functions.

http://docs.python.org/library/itertools.html

Mojaki
Posts: 1
Joined: Sat Apr 02, 2011 5:16 pm

Re: python permutations

Post by Mojaki » Sat Apr 02, 2011 5:44 pm

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
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.
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([1]) will return [[1]], 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:

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:]
I'm used to python 3, so you may need to tweak that.
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.

SirMeowMeow
Posts: 1
Joined: Tue Sep 20, 2011 8:46 pm

Re: python permutations

Post by SirMeowMeow » Tue Sep 20, 2011 11:41 pm

Set comprehension method:

Code: Select all

{x + y for x in '12345' for y in '56789'}
Written for Python 3.2

Post Reply