generating canonical list of tuples?

[Jason Orendorff]

> Ok, so I've tried a function which brute force cranks out the tuples by
> adding one to the last element, carrying it over, etc.  And I 
> wrote the exec method.  And I wrote the recursion method.  The exec
> runs at least six times faster than the brute force method.

I haven't been following this thread; perhaps someone already
suggested using a generator for this.

# Python 2.2 only
from __future__ import generators

def genWhiteTuples(total, blocks):
    """ The 'brute force' method, as a generator. """
    if total < blocks:
        # Trivial case
        return

    result = [1] * blocks
    running_total = blocks
    while 1:
        yield tuple(result)

        while running_total < total:
            # Easy.  Just increment the rightmost number.
            result[-1] += 1
            running_total += 1
            yield tuple(result)

        # Look for an element to reset.
        index = blocks - 1
        while index > 0:
            if result[index] > 1:
                # We found an element to reset.
                # (Must also increment the element to its left.)
                running_total = running_total - result[index] + 2
                result[index] = 1
                result[index-1] += 1
                break
            index -= 1
        else:
            # This means we're done.
            return

You can use a generator in a for statement,
just as you would use a list.

  for x1, x2, x3 in genWhiteTuples(10, 3):
      do_something(x1, x2, x3)

In this case, RAM consumption is low, because the tuples are
generated one at a time, as needed, instead of generating them
all at once and putting them in a list.  In fact, I can even:

  n = 0
  for t in genWhiteTuples(39, 6):
      n += 1  # count how many results
  print n

It runs in about 10 seconds on my machine, and doesn't use much RAM.
The result is 3262623.

If you *must* have a list, the syntax is pretty simple:
  L = list(genWhiteTuples(20, 10))

On my machine, this runs about as fast as your exec-based version,
and uses about the same amount of memory.

## Jason Orendorff    http://www.jorendorff.com/