ActiveState Code

Recipe 473808: randomized integer range iterator

iterate over all values of a range in random order.

related to http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/466177

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import array, random

TEADELTA     = 0x9e3779b9L
TEAROUNDS    = 32
TEASBOXSIZE  = 128
TEASBOXSHIFT = 7

class randrange(object):
    def __init__(self, start, stop):
        self.start = start
        self.max = stop - start
        self.sbox = array.array('I', [ random.randint(0, 0xffffffffL)
                                       for i in range(TEASBOXSIZE) ])
        bits = 0
        while (1 << bits) < self.max:
            bits += 1
        self.left = bits / 2
        self.right = bits - self.left
        self.mask = (1 << bits) - 1

        if TEASBOXSIZE < (1 << self.left):
            self.sboxmask = TEASBOXSIZE - 1
            self.kshift = TEASBOXSHIFT
        else:
            self.sboxmask = (1 << self.left) - 1
            self.kshift = self.left

    def __iter__(self):
        enc = 0
        for i in range(self.max):
            c = self.max
            while c >= self.max:
                c = enc
                enc += 1
                s = 0
                for j in range(TEAROUNDS):
                    s += TEADELTA
                    c ^= (self.sbox[(c ^ s) & self.sboxmask] << self.kshift)
                    c = (c + s) & self.mask
                    c = ((c << self.left) | (c >> self.right)) & self.mask
            yield self.start + c

    def __len__(self):
        return self.max

Discussion

this implements a modified (variable block size) TEA cipher by Niels Provos . a similar version in C is available in the libdnet Python extension module (http://libdnet.sf.net/) - see dnet.rand.xrange()

Comments

  1. 1. At 9:12 a.m. on 30 jan 2006, David Janes said: 
    import random

def randrange(start, stop):
    values = range(start, stop)

    while values:
        yield values.pop(random.randrange(len(values)))

    raise StopIteration

for x in randrange(0, 10):
    print x
  2. 2. At 4:29 p.m. on 1 feb 2006, Douglas Bagnall said:

    it is quicker to use random.shuffle()

    import random

def randrange(start, stop):
    values = range(start, stop)
    random.shuffle(values)

    while values:
        yield values.pop()

    raise StopIteration

for x in randrange(0, 10):
    print x
  3. 3. At 6:37 p.m. on 6 feb 2006, Dug Song (the author) said:

    hrr, i should have given an example... this is meant to handle cases where the results of range() will not fit in memory - e.g. a randomized walk over all values of the IP address space, or even sys.maxint, etc.

Sign in to comment