Generating combinations with repetitions

Charles Boncelet boncelet at udel.edu
Fri May 5 02:39:25 CEST 2000


Tomaz Ficko wrote:

> This is not quite what I meant. I want it to generate combinations not
> variations, order of the elements is irrelevant.
> Example: 121 is equal to 211 or 112.
> Anyway thanks.
>
> Tomaz

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)

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






More information about the Python-list mailing list