Previous Entry Share Next Entry
xkcd and shut-the-box

An xkcd comic from a while ago mentioned a "knapsack problem," and one reader (dhogarty) wrote some set enumeration code to tackle it.

Before I go further, I should mention that Knuth is the definitive reference here (as in most things), in particular Volume 4 which is now available only in fascicle form. If you haven't been reading the pre-fascicles just as soon as they're posted on the TAOCP web page, you're a sad sorry person who doesn't deserve to be called a computer scientist. (If you're not a computer scientist, read at least fascicle 4's chapter on the history of combinatorics; you can buy a hardcopy from amazon.)

The xkcd problem is called a "knapsack problem", but it's not, really; see Knuth's commentary around Algorithm F of (vol 4 fascicle 3a). We're generating multicombinations of n items taken from the m appetizers (repetition permitted). It's always worthwhile generating your options in strict lexicographic order to get a handle on duplicates; consult the history of combinatorics cited above for cautionary tales.

A compact way to generate multicombinations without duplicates is simply to require the output to be in lexicographic (sorted) order. For example, tweaking dhogarty's code only slightly:

def all_seqs(size, alphabet):
   for n,c in zip(xrange(len(alphabet)), alphabet):
     for s in all_seqs(size-1, alphabet[n:]) if size>1 else [[]]:
       yield [c]+s

You can wrap this in an iteration of sizes from 0 to infinity to generate multicombinations of all possible cardinalities.

A more elegant solution only generates multicombinations which sum properly (this is similar to Knuth's Algorithm F):

def ways_to_sum(total, menu):
    if total < 0: return
    if total == 0: yield []
    for (item,price),n in zip(menu, xrange(len(menu))):
        for tail in ways_to_sum(total-price, menu[n:]):
            yield [ item ] + tail

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

for solution in ways_to_sum(1505, menu):
    print solution

It's regrettable that the solution isn't unique. Bad Randall.

I've found lots of opportunities to generate "all possible solutions" in various contexts, and Python's generators have generally been an elegant means to express solutions. For example, I've been discussing "Shut the Box"; here's some code fragments to generate all possible plays for some board state:

def ways_to_sum(total, min_digit=1, max_digit=9):
    """Generate all the ways to sum to the given total using the digits
    `min` through `max` without repetitions.
    By default min and max are 1 and 9, respectively.

    >>> list(ways_to_sum(1))
    >>> list(ways_to_sum(2))
    >>> list(ways_to_sum(3))
    [[1, 2], [3]]
    >>> list(ways_to_sum(12))
    [[1, 2, 3, 6], [1, 2, 4, 5], [1, 2, 9], [1, 3, 8], [1, 4, 7], [1, 5, 6], [2, 3, 7], [2, 4, 6], [3, 4, 5], [3, 9], [4, 8], [5, 7]]
    for first in xrange(min_digit, min(max_digit+1, total)):
        for tail in ways_to_sum(total-first, min_digit=first+1, max_digit=max_digit):
            yield [ first ] + tail
    if min_digit <= total and total <= max_digit:
        yield [ total ]

def all_states(min_digit=1):
    """Generate all possible shut-the-box states."""
    if min_digit <= 9:
        for x in all_states(min_digit=min_digit+1):
            yield x
            yield [min_digit] + x
        yield []

The all_states() function generates the states in lexicographic order based on the set's binary representation (a9 a8 a7 ... a2 a1, to use Knuth's notation).

[This was originally going to be a comment on dhogarty's post, but after writing it I discovered that dhogarty had broken his wordpress installation sometime after 12 Sep 2008. I reverse-engineered the "Captcha-free" spam protection and fixed the Ajax URL in his page, but no dice. Querying the "Captcha-free" implementation with a python one-liner and performing a manual submission still loses. Maybe trackback will work.]


Log in

No account? Create an account