Tetris Random Generator: random.choice with permutations versus random.shuffle

Question

In some implementations of the game of Tetris, there is an algorithm called Random Generator which generates an infinite sequence of permutations of the set of one-sided tetrominoes based on the following algorithm:

Random Generator generates a sequence of all seven one-sided tetrominoes (I, J, L, O, S, T, Z) permuted randomly, as if they were drawn from a bag. Then it deals all seven tetrominoes to the piece sequence before generating another bag.

Elements of this infinite sequence are only generated when necessary. i.e. a random permutation of 7 one-sided tetrominoes is appended to a queue of tetrominoes when more pieces are required than the queue can provide.

I believe there are two primary methods of doing this in Python.

The first method uses itertools.permutations and random.choice

import itertools, random, collections
bag = "IJLOSTZ"
bigbag = list(itertools.permutations(bag))
sequence = collections.deque(random.choice(bigbag))
sequence.extend(random.choice(bigbag))
sequence.extend(random.choice(bigbag))
# . . . Extend as necessary

The second method uses only random.shuffle.

import random, collections
bag = ['I', 'J', 'L', 'O', 'S', 'T', 'Z']
random.shuffle(bag)
sequence = collections.deque(bag)
random.shuffle(bag)
sequence.extend(bag)
random.shuffle(bag)
sequence.extend(bag)
# . . . Extend as necessary

What are the advantages/disadvantages of either method, assuming that the player of Tetris is skilled and the Random Generator must produce a large sequence of one-sided tetrominoes?

Answer 1

There are 7! = 5040 permutations of a sequence of 7 distinct objects. Thus, generating all permutations is very costly in terms of both time complexity (O(n!*n)) and space complexity (O(n!*n)). However choosing a random permutation from the sequence of permutations is easy. Let's look at the code for choice from random.py.

def choice(self, seq):
    """Choose a random element from a non-empty sequence."""
    return seq[int(self.random() * len(seq))]  # raises IndexError if seq is empty

As you can see the calculation of the index is O(1) since len(seq) is O(1) for any sequence and self.random() is also O(1). Fetching an element from the list type in Python is also O(1) so the entire function is O(1).

---

On the other hand, using random.shuffle will swap the elements of your bag in-place. Thus it will use O(1) space complexity. However in terms of time complexity it is not so efficient. Let's look at the code for shuffle from random.py

def shuffle(self, x, random=None, int=int):
    """x, random=random.random -> shuffle list x in place; return None.

    Optional arg random is a 0-argument function returning a random
    float in [0.0, 1.0); by default, the standard random.random.
    """

    if random is None:
        random = self.random
    for i in reversed(xrange(1, len(x))):
        # pick an element in x[:i+1] with which to exchange x[i]
        j = int(random() * (i+1))
        x[i], x[j] = x[j], x[i]

random.shuffle implements the Fisher-Yates shuffle which, "is similar to randomly picking numbered tickets out of a hat, or cards from a deck, one after another until there are no more left." However the number of computations are clearly greater than the first method since len(x)-1 calls to random() must be made and it also requires len(x)-1 swap operations. Each swap operation requires 2 fetches from the list and the generation of a 2-tuple for unpacking and assignment.

---

Based on all of this information, I would guess that the first method mentioned uses up a lot of memory to store the permutations and requires O(n!*n) time complexity overhead, but in the long-run it is probably much more efficient than the second method and will likely keep the framerate stable in an actual implementation of a Tetris game since there will be less computations to do during the actual game loop. The permutations can be generated before the display is even initialized which is nice for giving the illusion that your game does not perform many computations.

---

Here I post finalized code using Tim Peters' suggestion of a generator and a circular buffer. Since the size of the circular buffer would be known before the buffer's creation, and it would never change, I did not implement all of the features that circular buffers usually have (you can find that on the Wikipedia article). In any case, it works perfectly for the Random Generator algorithm.

def random_generator():
    import itertools, random
    bag = "IJLOSTZ"
    bigbag = list(itertools.permutations(bag))
    while True:
        for ost in random.choice(bigbag):
            yield ost


def popleft_append(buff, start_idx, it):
    """ This function emulates popleft and append from
        collections.deque all in one step for a circular buffer
        of size n which is always full,
        The argument to parameter "it" must be an infinite 
        generator iterable, otherwise it.next() may throw
        an exception at some point """
    left_popped = buff[start_idx]
    buff[start_idx] = it.next()
    return (start_idx + 1) % len(buff), left_popped


def circular_peek(seq, start_idx):
    return seq[start_idx:len(seq)] + seq[:start_idx]


# Example usage for peek queue of size 5
rg = random_generator()
pqsize = 5
# Initialize buffer using pqsize elements from generator
buff = [rg.next() for _ in xrange(pqsize)]
start_idx = 0
# Game loop
while True:
    # Popping one OST (one-sided tetromino) from queue and 
    # adding a new one, also updating start_idx
    start_idx, left_popped = popleft_append(buff, start_idx, rg)
    # To show the peek queue currently
    print circular_peek(buff, start_idx)

Answer 2

I'd say that the time to shuffle a tiny list is simply trivial, so don't worry about it. Either method should be "equally random", so there's no basis for deciding there.

But rather than muck with both lists and deques, I'd use a tile generator instead:

def get_tile():
    from random import shuffle
    tiles = list("IJLOSTZ")
    while True:
        shuffle(tiles)
        for tile in tiles:
            yield tile

Short, sweet, and obvious.

Making that peekable

Since I'm old, when I hear "peekable queue" I think "circular buffer". Allocate the memory for a fixed-size buffer once, and keep track of "the next item" with an index variable that wraps around. Of course this pays off a lot more in C than in Python, but for concreteness:

class PeekableQueue:
    def __init__(self, item_getter, maxpeek=50):
        self.getter = item_getter
        self.maxpeek = maxpeek
        self.b = [next(item_getter) for _ in range(maxpeek)]
        self.i = 0

    def pop(self):
        result = self.b[self.i]
        self.b[self.i] = next(self.getter)
        self.i += 1
        if self.i >= self.maxpeek:
            self.i = 0
        return result

    def peek(self, n):
        if not 0 <= n <= self.maxpeek:
            raise ValueError("bad peek argument %r" % n)
        nthruend = self.maxpeek - self.i
        if n <= nthruend:
            result = self.b[self.i : self.i + n]
        else:
            result = self.b[self.i:] + self.b[:n - nthruend]
        return result

q = PeekableQueue(get_tile())

So you consume the next tile via q.pop(), and at any time you can get a list of the next n tiles that will be popped via q.peek(n). And there's no organic Tetris player in the universe fast enough for the speed of this code to make any difference at all ;-)