Welcome, guest | Sign In | My Account | Store | Cart

This code builds an iterator on the fly that will successfully return unique permutations of n integers, m at a time (nPm). It does not use recursion, so stack size is not a problem. Sample usage it= build(n,p)
it.next() # returns permutation

it=build(n) is the same as build(n,n) do it will generate n! unique permuatations.

I worte it over the weekend and have tested it reasonably for n upto 30 and p from 1 to 30

Python, 27 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27``` ```def build(n,m=0): " returns a generator that will successively return permutions on n integers m at a timt (nPr)" if (m==0): m = n source = """def perm(n,m):""" source = source + """\n r=set(range(1,n+1))""" # 1 indent already! source = source + """\n s0=r""" indent=1 for z in range(0,m): # main source build loop source= source + """\n""" + " ".ljust(indent)+ "for " + "i" + str(z) + " in s" + str(z) + ":" indent = indent+1 # build diff string diff="([" for k in range(0,z+1): diff=diff+ "i" + str(k)+"," diff=diff[:-1]+ "])" #print "diff = " + diff source=source + """\n"""+" ".ljust(indent)+"s"+str(k+1)+"=r.difference"+diff diff = diff[2:-2] #source = source + """\n""" + " ".ljust(indent) + "print " + diff source = source + """\n""" + " ".ljust(indent) + "yield " + diff+"," #print source obj=compile(source,'',"exec") exec(obj) return perm(n,m) ```

The code snippet actually builds a function with m nested loops and compiles teh internally build source to return a generator function.

The generator function will return a tuple on each call

Example

gen=build(5,2) gen.next() # will return 1,2 gen.next() # will return 1,3 ... gen(next() # last permutation retuend is (5,4)

Tested with Python 2.6 Created by nnarula on Mon, 22 Dec 2008 (MIT)

### Required Modules

• (none specified)