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