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

[Jeff Raven]

On Thu, 06 Apr 2000 16:04:14 -0400, Matthew Hirsch <meh9 at cornell.edu> 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:
>
>[0,1], [1,2], [2,3], [3,4]
>[0,2], [1,3], [2,4]
>[0,3], [1,4]
>[0,4]
>
>I have something like:
>
>n=5
>
>for first_choice in range(n):
>   for second_choice in range(first_choice+1,n):
>      for third_choice in range(second_choice+1,n):
>         print first_choice, second_choice, third_choice
>
>
>The problem is that I'll be dealing with large combinations of numbers 
>and it doesn't make sense to continue writing nested for loops.  I'm 
>trying to figure out something that generates all combinations, just 
>based on values of k and n.  Any ideas?
>
>Thanks for your help,
>Matt

Well, the following seems to work. Just call choices(5,2), etc.

The main idea is just to define a function which will let you
iterate through all the combinations (that's succ()). Once you've
got that, it's easy.

def succ(choice, n, k) :
    # Returns the 'next' increasing k-element subset of
    # {0 ... n-1} after choice. It does so by working from
    # the end of the list, trying to increment elements.
    # Once it finds one it can increment, it then works
    # back towards the end filling in the remaining
    # values.
    index = k - 1
    while index >= 0 :
	choice[index] = choice[index] + 1
	if choice[index] <= n - k + index :
	    break
	index = index - 1
    else:
	return 0
    while index < k - 1 :
	choice[index + 1] = choice[index] + 1
	index = index + 1
    return 1

def choices(n, k) :
    # Returns a list consisting of all k-element (ordered)
    # subsets of {0 ... n-1}.
    result = []
    if k > n :
	return result

    current = range(k)
    while 1 :
	result.append(current[:])
	if not succ(current, n, k) :
	    break
    return result

Hope that helps,
Jeff Raven