generating canonical list of tuples?

[Steve Holden]

"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.
>
> If "dimension" is a fixed number, this is easy.  In the case where
dimension
> is 3, this can be written as:
>
> [ (a,b,c) for a in range(1,4) for b in range (1,5-a) for c in
> range(1,6-a-b) ]
>
> But (and here is the REAL question)...  how does one do this when
dimension
> is a variable?
>
> Option 1:  Recursion.  Recursion will cause a memory explosion when the
> limit and dimension begin to grow, and so this isn't a good solution.

I don't see why you make this assertion. Surely an exhaustive search for
dimension 32 could be performed with no more than 33 active calls. Of course
the space required to store the list will increase as limit increases, but
since you want to return the list that's a given anyway.

> Option 2:  Exec.  Construct a line of python code dynamically based on the
> above example, and exec it.  Would this be considered a good solution?

Perhpas by some, but my own feeling is that exec (and to a lesser extent
eval(), which might be another choice for this problem) should be reserved
as an absolute last resort.

> Option 3:  ???
>
I note that you regard (1,1,2) as different from (1,2,1) and (2,1,1), so
ordering is clearly important. This makes it quite a knotty problem.

> Is there a pythonic way of doing this?
>
Go for recursion!

regards
 Steve
--
http://www.holdenweb.com/