Description: given positive integers h and k, return an iterator that produces tuples of k integers (i[1], ... ,i[k]) such that sum(i[j], j=1..k) = h and 0 < i[1] < i[2] < i[3] < ... . This kind of set occurs often as indexes of summation in mathematical problems.

def ordered_tuples(k,h,start=1):
    if k<1:
        return
    if k==1:
        yield (h,)
        return
    for i in range(start,(2*h - k*(k-1))/(2*k) + 1):
        for js in ordered_tuples(k-1,h-i,i+1):
            yield (i,) + js

This is one of my favorite pieces of code ever! It's just a snippet, but it solved a real problem in a clever, compact way. We make essential use of the Python notion of a generator (recognized by the "yield" statements). I was delighted when it actually worked -- not because I don't trust my code, but because I wasn't sure that Python would support multiple instances of the same generator with different state. But it does, and I'm happy.

If you don't see the big deal, try coding this in C, C++, or Java. A generator is a kind of coroutine, which the aforementioned popular languages don't have. Handy things, coroutines.

Note: One could easily use a recursive function to simply build a list of all the tuples. But I was using millions of them and I would have run out of memory. This way we run in constant space.

$ python

>>> (paste function here)

>>> for x in ordered_tuples(1,15): print x
...
(15,)

>>> for x in ordered_tuples(2,15): print x
...
(1, 14)
(2, 13)
(3, 12)
(4, 11)
(5, 10)
(6, 9)
(7, 8)

>>> for x in ordered_tuples(3,15): print x
...
(1, 2, 12)
(1, 3, 11)
(1, 4, 10)
(1, 5, 9)
(1, 6, 8)
(2, 3, 10)
(2, 4, 9)
(2, 5, 8)
(2, 6, 7)
(3, 4, 8)
(3, 5, 7)
(4, 5, 6)
>>> for x in ordered_tuples(4,15): print x
...
(1, 2, 3, 9)
(1, 2, 4, 8)
(1, 2, 5, 7)
(1, 3, 4, 7)
(1, 3, 5, 6)
(2, 3, 4, 6)

>>> for x in ordered_tuples(5,15): print x
...
(1, 2, 3, 4, 5)

>>> for x in ordered_tuples(6,15): print x
...
(no output)