Generate all k-subsets of an n-set sequentially


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



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.