8
\$\begingroup\$

I am new to Python and want to have a "pythonic" coding style from the very beginning. Following is a piece of codes I wrote to generate all combinations and permutations of a set of symbols, e.g. abc or 123. I mainly seek for suggestions on code style but comments on other aspects of codes are also welcome.

import random as rd
import math as m
def permutationByRecursion(input, s, li):
    if len(s) == len(input):
        li.append(s)
    for i in range(len(input)):
        if input[i] not in s:
            s+=input[i]
            permutationByRecursion(input, s, li)
            s=s[0:-1]

def combinationByRecursion(input, s, idx, li):
    for i in range(idx, len(input)):
        s+=input[i]
        li.append(s)
        print s, idx
        combinationByRecursion(input, s, i+1, li)
        s=s[0:-1]

def permutationByIteration(input):
    level=[input[0]]
    for i in range(1,len(input)):
        nList=[]
        for item in level:
            nList.append(item+input[i])
            for j in range(len(item)):
                nList.append(item[0:j]+input[i]+item[j:])
        level=nList
    return nList

def combinationByIteration(input):
    level=['']
    for i in range(len(input)):
        nList=[]
        for item in level:
            nList.append(item+input[i])
        level+=nList
    return level[1:]



res=[]
#permutationByRecursion('abc', '', res)
combinationByRecursion('abc', '', 0, res)
#res=permutationByIteration('12345')
print res
print combinationByIteration('abc')
\$\endgroup\$
  • 1
    \$\begingroup\$ Just in case you didn't know, python has permutations and combinations in itertools package in stdlib. \$\endgroup\$ – rahul Jun 21 '12 at 7:18
  • \$\begingroup\$ @blufox, i am aware of it, just wrote the program for practice. \$\endgroup\$ – sma Jun 22 '12 at 14:54
  • \$\begingroup\$ @pegasus, I know blufox and cat_baxter pointed out itertools and I assume you've seen it but for anybody else the python docs contain code samples for both permutation and combination \$\endgroup\$ – IamAlexAlright Jul 4 '12 at 9:40
7
\$\begingroup\$

A small change, In python, it is more idiomatic to use generators to generate items rather than to create lists fully formed. So,

def combinationG(input):
    level=['']

You could directly enumerate on each character here.

    for v in input:
        nList=[]
        for item in level:
            new = item + v

Yield is the crux of a generator.

            yield new
            nList.append(new)
        level+=nList

Using it

print list(combinationG("abc"))

Note that if you want access to both index and value of a container you can use for i,v in enumerate(input)

Here is the recursive implementation of permutation. Notice that we have to yield on the value returned by the recursive call too.

def permutationG(input, s):
    if len(s) == len(input): yield s
    for i in input:
        if i in s: continue
        s=s+i
        for x in permutationG(input, s): yield x
        s=s[:-1]


print list(permutationG('abc',''))
| improve this answer | |
\$\endgroup\$
10
\$\begingroup\$

Just use the standard modules :)

import itertools
for e in itertools.permutations('abc'):
    print(e)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ thanks, I am aware of it. Just wrote it for practicing python \$\endgroup\$ – sma Jun 22 '12 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.