Flying Symbols

Generators are an interesting language feature, somewhat related to the concept of lazy evaluation. Essentially, they are a way to lazily generate a sequence of values using a persistent local function state. Generator functions ‘pause’ by yielding a value, and ‘resume’ at the next line when another value is needed.

The classic example of a generator in Python is the following:

def fib():
    a, b = 0, 1
    while 1:
        yield b
        a, b = b, a+b

This fibonacci sequence generator is an example of an infinite lazy sequence. If we used this in a loop, the iterator would never terminate, so we would have to break out of the loop. To make this infinite sequence terminate, let’s wrap it in another iterator:

def fibs_up_to(n):
    for f in fib():
        if f > n:
            break
        else:
            yield f

When the infinite fib() generator yields a value greater than our threshold, the fibs_up_to() generator breaks out of the loop, and reaches the end of the function. When evaluation reaches the function bottom, the generator terminates itself and any enclosing ‘for’ loop.

In the following snip from the python shell, we see that the next fibonacci number (610) caused our wrapper iteration to break out of its loop and terminate the outer print loop.

>>> for f in fibs_up_to(500):
...     print '%d ' % (f,),
...
1  1  2  3  5  8  13  21  34  55  89  144  233  377

Now, with the background info out of the way, let’s dive into the fun part: recursive generators! The first time I noticed this pattern was while working on a fun problem Randall Munroe posted on his xkcd webcomic:

One (inefficient) way of attacking this problem is to generate all sequences of orders, and test each to see whether it totals the target price. As it turns out, generating all sequences of a set is surprisingly easy using a recursive generator:

def all_seqs(size, alphabet):
    if size == 1:
        for c in alphabet:
            yield [c]
    else:
        for c in alphabet:
            for s in all_seqs(size - 1, alphabet):
                yield [c]+s

>>> for s in all_seqs(3, ‘ABC’):
…     print s
…
['A', 'A', 'A']
['A', 'A', 'B']
['A', 'A', 'C']
['A', 'B', 'A']
['A', 'B', 'B']
['A', 'B', 'C']
['A', 'C', 'A']
['A', 'C', 'B']
['A', 'C', 'C']
['B', 'A', 'A']

The generator starts with the terminal case: if the size of the sequence is one, simply yield each option element, one at a time. The recursive case is only slightly more complicated: prepend each option element to all of the sequences one smaller than the current size. Recursively calling the generator allows this to be represented very simply, without needing to waste memory on creating a complete list of all the one-smaller sequences.

While interesting, this approach has a problem when applied to the xkcd problem: it generates duplicates…

[('Fruit', 215), ('Wings', 355), 
    ('Wings', 355), ('Sampler', 580)]
[('Fruit', 215), ('Wings', 355), 
    ('Sampler', 580), ('Wings', 355)]
[('Fruit', 215), ('Sampler', 580), 
    ('Wings', 355), ('Wings', 355)]
…

These repeated results (12 in all) are all the permutations of the multiset with 1 Mixed Fruit, 2 Hot Wings, and 1 Sampler. So, what we’re really interested in is a generator that will yield successive multisets, thus making sure we don’t waste time evaluating multiple equivalent orders.

Like most abstract data structures, a multiset has several different concrete representations. To investigate this, we will look at how to represent several multisets taken from the set {A, B, C} in three different forms:

Element List	Item Counts	Count List
[A,A,A,C]	{A:3, C:1}	[3,0,1]
[A,B,B,C]	{A:1, B:2, C:1}	[1,2,1]
[B,B,B,C,C,C]	{B:3, C:3}	[0,3,3]

The item counts and count list both represent sets with repeated elements, related in the same way that sparse and dense matrices are. For sparser multisets, the item counts are better, but for denser sets, the count list saves a little space by not carrying a reference to the element around with each count.

First, we’ll take a look at how to generate the simple element list with a recursive generator. Here’s the code:

def all_multisets(cardinality, options):
    def all_multi_rec(card, ind):
        if card==0:
            yield []
        else:
            for i in xrange(ind, len(options)):
                for m in all_multi_rec(card-1,i):
                    m.append(options[i])
                    yield m
    for m in all_multi_rec(cardinality, 0):
        yield m

This is slightly more complicated than generating sequences, but still fairly simple. The recursive generator is the inner function ‘all_multi_rec’. The parameters to the outer function are the desired multiset cardinality (number of items in the multiset), and the options from which to take values. The recursion hinges on maintaining an index which is used to limit the already-used items from being re-included. in the recursive path, the ‘else’ in the above code, only items at the current index and beyond are added.

How close are we to being able to write a simple solution now? This close:

menu = [('Fruit', 215), ('Fries', 275),
        ('Salad', 335), ('Wings', 355),
        ('Sticks', 420), ('Sampler', 580)]

for c in xrange(1,8):
    for m in all_multisets(c, menu):
        if sum(x[1] for x in m) == 1505:
            print m

…
…
[('Sampler', 580), ('Wings', 355), 
    ('Wings', 355), ('Fruit', 215)]
[('Fruit', 215), ('Fruit', 215), 
    ('Fruit', 215), ('Fruit', 215), 
    ('Fruit', 215), ('Fruit', 215), 
    ('Fruit', 215)]

Admittedly, hard-coding the cardinality limits is clunky… maybe more on that later. For something more to chew on, here are versions for the other two representations of multisets:

def all_multiset_counts(cardinality, length):
    def all_multi_rec(card, ind):
        if card == 0:
            yield [0,]*length
        else:
            for i in range(ind, length):
                for m in all_multi_rec(card-1, i):
                    m[i] += 1
                    yield m
    for m in all_multi_rec(cardinality, 0):
        yield m

def all_multisets_dict(cardinality, options):
    def all_multi_rec(card, ind):
        if card==0:
            yield {}
        else:
            for i in xrange(ind, len(options)):
                for m in all_multi_rec(card-1, i):
                    item = options[i]
                    if m.has_key(item):
                        m[item] += 1
                    else:
                        m[item] = 1
                    yield m
    for m in all_multi_rec(cardinality, 0):
        yield m

Thoughts anyone? Hope you enjoyed,

-DH