Algorithm: combinations of (k) taken from (n) values

[Charles Boncelet]

Matthew Hirsch wrote:

> Hi All,
>
> Onto the next question...
>
> Can anyone think of an algorithm to store as lists all possible
> combinations of k numbers taken from n possible numbers.  For example,
> given 5 values, I want to choose 2.  The number of possible combinations
> is given by 5!/(3!2!)=10.  They are:
>

Funny you should ask, since I just wrote one two days ago:

def combs(n,k=None):
    """returns sorted list of k items taken from n."""
    if k==None:
        k=n
    l = []
    for c in range(n):
        l.append([c])
    for i in range(k-1):
        li = []
        for c in l:
            for j in range(c[-1]+1,n):
                li.append(c+[j])
        l = li
    return l

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