generating canonical list of tuples?

[Alex Martelli]

"Joshua Muskovitz" <joshm at taconic.net> wrote in message
news:3c34cafa_2 at corp.newsgroups.com...
> Here's what I'm trying to do...
>
> create "magicFunction(limit, dimension)" to return a list of tuples.  Each
> tuple contains exactly "dimension" elements, all positive integers.  The
sum
> of these elements must be less than or equal to "limit".
>
> for example, magicFunction(5,3) should return:
> [ (1,1,1), (1,1,2), (1,1,3), (1,2,1), (1,2,2), (1,3,1), (2,1,1), (2,1,2),
> (2,2,1), (3,1,1) ]
>
> The order of the resulting tuples is unimportant.

OK, quite clear.

> If "dimension" is a fixed number, this is easy.  In the case where
dimension
    ...
> But (and here is the REAL question)...  how does one do this when
dimension
> is a variable?

Think "counting in a variable base" -- it's often a good mindset in
such 'enumeration problems'.  In counting we increment each digit as
far as possible, then when the digit would overflow we reset it to
the minimum value and proceed to the next most significant digit.

Here, a 'digit overflows' when the total reaches the limit, so...:

def magicFunction(limit, dimension):
    if limit < dimension: return []
    current = [1]*dimension
    results = [tuple(current)]

    def total(current):
        import operator
        return reduce(operator.add, current)

    while 1:
        index = 0
        while index < dimension:
            if total(current) < limit:
                current[index] += 1
                results.append(tuple(current))
                break # exit inner loop, continue outer loop
            elif current[index] > 1:
                current[index] = 1
            index += 1
        else: return results

Rather than recomputing the total() each time, you could also
maintain it incrementally.  This also looks like a good
candidate to make into a simple-generator, by just changing
the .append (and the first assiment to results) into yield
statements and making the return statements expressionless --
but that, obviously, wouldn't change the algorithm, just package
it up in a potentially more usable way.


Alex