Generating combinations with repetitions

[Jeff Raven]

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:
>
>class Combinations(UserList):
>    """list of combinations of k items taken from n. If repetition=1,
>    then repetitions are allowed. I.e., [1,2,2,3] is one of the
>    combinations generated by Combinations(5,4,repetition=1).  """
>    def __init__(self,n,k=None, repetition=0):
>        if k == None:
>            k = n
>        if k == 0:
>            l = []
>        else:
>            l = []
>            for i in range(n):
>                l.append([i])
>            for i in range(k-1):
>                li = []
>                for p in l:
>                    if repetition:
>                        for m in range(p[-1],n):
>                            li.append(p+[m])
>                    else:
>                        for m in range(p[-1]+1,n):
>                            li.append(p+[m])
>                l = li
>        UserList.__init__(self,l)
>

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.

Jeff Raven