two flies in one hit: working around goto and grid point generation

Anton Vredegoor anton at vredegoor.doge.nl
Mon Mar 8 16:28:43 CET 2004


I've been trying to avoid posting this code because it enables
continuations alike coding and can be used for state machines. The
applications are endless and since I have no idea how to wrap this
into a reversible iterator with state repositioning and storing states
as integers I thought it too soon to post about it.

The idea is very simple but I'm having problems with the terminology
and the concepts that are involved. However this group is constantly
knocking on my door with threads like "generating points on a grid -
efficiently" or "Working around a lack of 'goto' in python" so I
thought it best to just throw it in the ring and let others decide
about how to get a grip on it.

The code is about "generating all n-tuples" as described by Knuth in
his new (unpublished ?) book, but now using different ranges for each
position. This way one could recode nested loops as a single loop,
reversely iterate nested loops, store nested loop positions ("states")
as integers and set a nested loop to a specific state, generate points
on a grid of differently sized axes and what else.

Ok, enough speculations and hype, below is some code, I hope someone
sees the applicability of the concept and can turn it into a fast
generator class that could be used as a programmable state machine.

Yes, I've been posting this code before, but now I see the other
possibilities of it. Please tell me if I'm onto something or just
hallucinating or reinventing the wheel. FWIW it has a lot in common
with ideas that are used in Numerical Python.

Anton

def rank(L,bases):
    res,multiplier = 0,1
    for x,b in zip(L[::-1],bases[::-1]):
        res += x*multiplier
        multiplier *= b
    return res

def unrank(d,bases):
    res = []
    for b in bases[::-1]:
        d,m = divmod(d,b)
        res.append(m)
    return res[::-1]

def test():
    bases = [4,3,2]
    n = reduce(lambda x,y: x*y,bases)
    for i in range(n):
        x = unrank(i,bases)
        print i,x
        assert i == rank(x,bases)

if __name__=='__main__':
    test()

output:

0 [0, 0, 0]
1 [0, 0, 1]
2 [0, 1, 0]
3 [0, 1, 1]
4 [0, 2, 0]
5 [0, 2, 1]
6 [1, 0, 0]
7 [1, 0, 1]
8 [1, 1, 0]
9 [1, 1, 1]
10 [1, 2, 0]
11 [1, 2, 1]
12 [2, 0, 0]
13 [2, 0, 1]
14 [2, 1, 0]
15 [2, 1, 1]
16 [2, 2, 0]
17 [2, 2, 1]
18 [3, 0, 0]
19 [3, 0, 1]
20 [3, 1, 0]
21 [3, 1, 1]
22 [3, 2, 0]
23 [3, 2, 1]





More information about the Python-list mailing list