Permutations algoritm?

[Stuart D. Gathman]

On Fri, 15 Nov 2002 15:18:25 -0500, sismex01 wrote:

> Does anybody have a clear, simple, permutations algorithm in Python?

If you Google (google.com) comp.lang.python for "Python Permutation",
you will get lots of discussion.

However, I'll copy in the algorithm I liked best for permuting an
an arbitrary list: (STL algorithm works great on range(n))

Alex Martelli wrote:

*blink* -- yes... nonobvious but it works -- slicing the time to
permute range(10) [need to start using more substantial examples
here:-)] from 19.63 to 12.22 on my box.  However, the same trick
also works for the modifying-in-place "myperm", slicing ITS time
for permuting range(10) from 14.10 down to 10.13 (I'm only using
Python 2.3 now for all of these measurements).

And, applying Anton's trick to Duncan's best micro-optimization
of his in-place-modification approach:

def mypermy(l):
    pop, insert, append = l.pop, l.insert, l.append

    def halfperm():
        ll = l
        llen = len(ll)
        if llen <= 2:
            yield ll
            return
        aRange = range(llen)
        v = pop()
        for p in halfperm():
            for j in aRange:
                insert(j, v)
                yield ll
                del ll[j]
        append(v)

    for h in halfperm():
        yield h
        h.reverse()
        yield h
        h.reverse()

ITS time to permute range(10) is reduced from 12.13 to 9.59
Yes we do need two .reverse calls -- halfperm's dependent
on the list not being modified under it -- the alternative
way to write the final loop:

    for h in halfperm():
        p = h[:]
        yield p
        p.reverse()
        yield p

takes 11.03 to permute range(10), once again showing (here,
to me at least, less surprisingly) that modifying in-place
and undoing the modification is faster than making a new
list (a copy) and modifying the copy.


Alex


-- 
Stuart D. Gathman <stuart at bmsi.com>
Business Management Systems Inc.  Phone: 703 591-0911 Fax: 703 591-6154
"Confutatis maledictis, flamis acribus addictis" - Mozart background
song for the Microsoft "Where do you want to go from here?" commercial.