Generating combinations with repetitions

[Charles Boncelet]

Jeff Raven wrote:

> On Fri, 05 May 2000 10:39:25 +1000, Charles Boncelet <boncelet at udel.edu> wrote:
> >
> >Here is a slight variation to the combinations algorithm I posted a
> >couple of weeks ago, now as a Class:
> >
> >(python code deleted)
>
> Well, it works, but it doesn't fare too well when compared to the
> alternatives. Calculating 20 choose 20 this way (with or without
> repetitions) consumes far more memory and time than is really
> necessary.
>

You're exactly right.  It hadn't occurred to me that the intermediate
results my algorithm computed could be *much* larger than the
final resurt.  E.g., len(choices(20,20))=1, but along the way my
algorithm computes an array of size choices(20,10) = 184756.

I had an algorithm similar to yours, but deleted it in favor of the
more "elegent" solutiion. :-(

BTW, rchoices(20,20) (with repetitions) generates a list of
68923264410 items, too big for my computer, no matter what
algorithm I use.

    Charlie Boncelet

--
------
Charles Boncelet, University of Delaware,
On sabbatical at ADFA, Canberra Australia,
Home Page: http://www.ece.udel.edu/~boncelet/