Advanced Search

Generate all k-subsets of an n-set sequentially

/ Published in: Python
Save to your folder(s)

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. def generate_k_subsets(n,k):
  2.     """
  3.     Generate all k-subsets of an n-set sequentially.
  4.     Reference:
  5.         http://www.math.upenn.edu/~wilf/website/CombinatorialAlgorithms.pdf
  6.         Chapter 3
  7.     """
  8.     m, h  = 0, k
  9.     a = range(k)
  10.     yield a
  11.     while True:
  12.         if m < n-h: h = 1
  13.         else: h += 1
  14.         m = a[k-h] + 1
  15.         for j in range(h): a[k+j-h] = m + j
  16.         yield a
  17.         if a[0] == n - k:  break

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.