Loop from 'aaaa' to 'tttt' ?

[Anton Vredegoor]

Lars Schaps <tuffi23 at gmx.de> wrote:

>In my program in need a loop from 'aaaa' over
>'aaac', 'aaag', 'aaat', 'aaca' to 'tttt'.
>(Possible characters 'a', 'c', 'g' and 't')
>
>One idea i had is to take a number n with the base of
>4 and use 
>
>t= string.translate( '0123', 'acgt')
>string.translate( n, t)
>
>But i don't know how to convert from base10 to base4.
>
>Has anyone a idea?

Well yes, but it's kind of hard to explain, or the idea smells like
something from pellucidar, or I'm just not so good at explaining (see
some other posts of mine to verify that!). I've been posting versions
of a script here but haven't got much feedback about it. I've updated
it a bit recently so maybe it's time to try again.

Normal counting proceeds like there's an infinite row of zeros to the
left of a number. So the numbers 1, 01, 001 ,0001 etc. are all
considered to be equal and equal to 1. There's another possibility to
count, lets call these numbers antonian numbers for lack of a better
name. It goes like this, assuming base 10, with the normal digits:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, and next -surprisingly- what follows is
*not* "10" but its "00". Why? because in normal counting there already
was an "invisible" leading zero that got increased to "1" but in my
system there where no leading zero's to begin with, so a zero is added
to the left.

So counting goes on:

... 7, 8, 9, 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, etc.

Since this way of counting can sometimes be useful - I discovered it
while trying to uniquely identify series of turns of a rubiks cube -
I've written a script to "rank" and "unrank" such sequences, using a
reference list of unique items as "digits". I have not yet found a way
to write this all up in an eyeball friendly way in Python, but I think
the script can already be used. Probably now someone will post
something that turns all this into a selfexplanatory oneliner by
affixing a standard "1" digit  in front, but hey, I'm assuming this
era hasn't got such a script yet :-)


Anton


class Rank:
    
    """ 
        ranks and unranks lists, it has to be initialized with a 
        reference list wherein each item occurs once
    """
    
    def __init__(self,items):
        #initialize with reference list
        self.items = items
        self.base =  len(items)
        self.lookup = dict([(y,x) for x,y in enumerate(items)])
        self.asstring = True
        try: self.items+''
        except TypeError: self.asstring = False
    
    def unRank(self,n):
        #create the list with rank n
        result, base, items = [], self.base, self.items
        while n >= 0:
            i = (n-base)/base
            result.append(items[n-base*(i+1)])
            n = i
        result.reverse()
        if self.asstring: return "".join(result)
        else: return result

    def rank(self,L):
        #compute the rank of list L
        index, base = self.items.index, self.base
        lookup =  self.lookup
        i = lookup[L[0]]
        for x in L[1:]:  i = lookup[x]+base*(i+1)
        return i

def test():
    R = Rank("ACGT")
    start, end = R.rank("AAAA"),R.rank("TTTT")
    for i in xrange(start,end+1):
        print R.unRank(i)
    
if __name__=='__main__':
    test()