Home Original page

Improve this recursive code please!

Steven Taschuk staschuk at telusplanet.net
Sun May 11 15:51:50 EDT 2003 
Quoth Anton Vredegoor:
> Steven Taschuk <staschuk at telusplanet.net> wrote:
> 
> [posts nice successor function]
> 
> >distinct but all bricks the same; it produces results in sorted
> >order; it holds only one result in memory at a time, avoiding a
> 
> No, it doesn't produce the results in sorted order, not even in
> reverse sorted order :-)

Doesn't it?  Certainly
    # Change (..., m,   ...bunch of 0s...,   n)     (where m > 0)
    # into   (..., m-1, n+1, ...bunch of 0s...)
transforms the current tuple into one which is after it in reverse
lexicographic order (which I think is the order the OP wanted).
Assuming it produces all desired tuples, how can it not produce
them sorted?

(Reversing the order of the output is easy; just left-right
reverse the transformation above and the initial state.)

  [...]
> One question that remains is: Do we have enough mathematicians in this
> group to count the number of arrangements that are produced this way?

Not a mathematician, but the number of arrangements for m bricks
and n bins is
    m+n-1 choose m
Proving this by induction is not difficult, though as usual for
such proofs, neither is it particularly, er, insight-bringing.  I
don't see a combinatoric proof at the moment, but no doubt there's
a nice one.

-- 
Steven Taschuk                                7\ 7'Z {&~         .
staschuk at telusplanet.net                        Y r          --/hG-
                                            (__/ )_             1^1`
More information about the Python-list mailing list