title: Manual generation of r-combinations in Python
body: <p>I am attempting to manually generate r-combinations (<strong>it is absolutely essential to me that I manually generate these and not use itertools</strong>).</p>
  
  <p>This is my current block of code:</p>
  
  <pre><code>def rcombs(items, r):
      n = len(items)
      s = []
      permuted_items = []
      for i in xrange(0, r):
          s.append(i)
  
      for i in xrange(1, C(n,r)):
          m = r - 1
          max_val = n - 1
          while (s[m] == max_val):
              m = m - 1
              max_val = max_val - 1
  
          s[m] = s[m] + 1
  
          for j in xrange(m + 1, r):
              s[j] = s[j-1] + 1
  
          temp_ = []
          for k in s:
              temp_.append(items[k])
  
          permuted_items.append(temp_)
  
      return permuted_items
  
  def C(n, r):
      return math.factorial(n) / (math.factorial(r) * math.factorial(n - r))
  </code></pre>
  
  <p>However, it seems to miss some combinations. An easy example is when finding 1-combinations and 2-combinations; the algorithm returns:</p>
  
  <pre><code>    items = [0, 1, 2, 3, 4]
  
      1 -combinations:
      [[1], [2], [3], [4]]
  
      2 -combinations:
      [[0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
  </code></pre>
  
  <p>For 1-combinations [0] is missing, and for 2-combinations [0,1] is missing.</p>
  
  <p>All help appreciated.</p>