Posted By

bingjian on 08/03/09


Tagged

algorithm combinatorics


Versions (?)

Generate all k-subsets of an n-set sequentially


 / Published in: Python
 

  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  

You need to login to post a comment.