How to use a 5 or 6 bit integer in Python?

[Anton Vredegoor]

Glen Wheeler <adsl5lcq at tpg.com.au> wrote:

>  Well, I'm a researcher for an Australian university (University of
>Wollongong) and my current task is to enumerate every possible 6 digit
>binary Gray code.

It is possible to write a function that turns every integer into its
"reflected" form so that the normal enumeration of the integers
corresponds to a gray code (successors that differ only in one bit
position) sequence. This can be done without enumerating them all.

Here's some code from a book by Kreher and Stinson (Combinatorial
ALgorithms) which I translated into Python from the pseudo-code in the
book. I made some adaptations and came up with this:

import sets

def unrank(n,r):
    T,b1 = [],0
    for i in range(n-1,-1,-1):
        b0 = r/(2**i)
        if b0 != b1: 
            T.append(n-i-1)
        b1 = b0
        r -= b0*2**i
    return T

def rank(n,T):
    S = sets.Set(T)
    r,b = 0,0
    for i in range(n-1,-1,-1):
        if n-i-1 in S:
            b = 1-b
        if b == 1:
            r += 2**i
    return r

def reflect(n,r):
    S = sets.Set(unrank(n,r))
    L = ["01"[i in S] for i in range(n)] 
    return int("".join(L),2)

def test():
    n = 2**6
    T = [None]
    for i in range(100):
        U = unrank(n,i)
        print i, reflect(n,i),U
        assert rank(n,U) == i
        assert len(sets.Set(T) ^ sets.Set(U)) == 1
        T = U

if __name__=='__main__':
    test()

>  I hope that's sated your curiosity for now :).  If you'd like any
>more information, or if anyone else would like to know anything about
>this, then I'll be happy to correspond with them.  I don't know how
>on-topic it is for c.l.py.

If it's interesting and provides an excuse for exercising our
programming skills in our favorite language, it's on topic. It's even
on topic if it's outrageously off-topic enough, so take your pick :-)

I guess I must have missed something because if the problem's solution
can be looked up in a book it probably is not what you are looking
for. So why is it not enough to have an indexing function and why do
you need to have all values literally?

Anton