Combinations

Python code to generate k-combinations from N numbers. Included is a recursive and an iterative version. It’s easy.

def choose_rec(n,k):
  a = range(k)
  choose_rec(0,n,k,0,a)

def choose_rec_aux(col,n,k,start,a):
  if col == k:
    print a
    return
  for i in range(start,n-k+col+1):
    a[col] = i
    choose_rec_aux(col+1,n,k,i+1,a)

def choose_iter(n,k):
  a = range(k)
  f = range(n-1,n-k-1,-1)
  f.reverse()

  print a
  while True:
    i = k-1
    while i >= 0 and a[i] == f[i]:
      i = i - 1
      if i < 0:
        return
      else:
        a[i] = a[i] + 1
        for i in range(i+1, k):
          a[i] = a[i-1] + 1
      for j in range(a[i], n):
        a[i] = j
        print a
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s