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
Download
Copy to clipboard1 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,'<in line 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
