Permutations algoritm?

[Duncan Smith]

"Stuart D. Gathman" <stuart at bmsi.com> wrote in message
news:ar3rgb$cn8$1 at nntp2-cm.news.eni.net...
> 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.

I'm not sure what I might have posted on this before, but I spent some time
on this a while back.  I'm pretty sure I was using a lex ordering.  I was
only concerned with the combinations of integers in the range 1 to n, but
probably easy enough to adapt.

---------------------------------------------------------------
def combinations(n, k):
    current = range(1, k + 1)
    max = range(n - k + 1, n + 1)
    while current != max:
        for number in current:
            print '%2d'% (number),
        print
        index = -1
        if current[index] != max[index]:
            current[index] = current[index] + 1
        else:
            for indices in range(-2, -k - 1, -1):
                if current[indices] != max[indices]:
                    current[indices] = current[indices] + 1
                    for other_indices in range(indices + 1, 0):
                        current[other_indices] = current[indices] +
other_indices - indices
                    break
    for number in max:
        print '%2d'% (number),
--------------------------------------------------------------------

eg.

>>> combinations(6,3)
 1  2  3
 1  2  4
 1  2  5
 1  2  6
 1  3  4
 1  3  5
 1  3  6
 1  4  5
 1  4  6
 1  5  6
 2  3  4
 2  3  5
 2  3  6
 2  4  5
 2  4  6
 2  5  6
 3  4  5
 3  4  6
 3  5  6
 4  5  6
>>>

Or doing some bit-shifting to speed it up a bit.  Different output, but the
idea is reasonably obvious (although it now appears to be reverse lex
ordering or some-such; it's a while since I wrote this).

----------------------------------------------------------
def combinations2(n, k):
    comb = gmpy.mpz(1)
    for i in range(k):
        comb = comb.setbit(i)  #first combination
    count = 1
    while count != k:
        print comb.digits(2)
        s_len = len(comb.digits(2)) - 1
        for i in range(s_len, n-1):
            comb = comb.setbit(i, 0)
            comb = comb.setbit(i+1)
            print comb.digits(2)
        count = 0
        for i in range(n-1, 0, -1):
            if comb.getbit(i) == 1:
                comb = comb.setbit(i, 0)
                count += 1
            else:
                s_len = len(comb.digits(2)) - 1
                comb = comb.setbit(s_len, 0)
                for j in range(count + 1):
                    comb = comb.setbit(s_len + j + 1)
                break

---------------------------------------------------------

>>> bit_stuff.combinations2(6,3)
111
1011
10011
100011
1101
10101
100101
11001
101001
110001
1110
10110
100110
11010
101010
110010
11100
101100
110100
111000
>>>
------------------------------------------------------------------

Comments on my crappy code are welcome.

Duncan