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,'<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

Created by nnarula on Mon, 22 Dec 2008 (MIT)
Python recipes (4591)
nnarula's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks