title: Find the index of a given combination (of natural numbers) among those returned by `itertools` Python module
body: <p>Given a combination of <code>k</code> of the first <code>n</code> natural numbers, for some reason I need to find the position of such combination among those returned by <code>itertools.combination(range(1,n),k)</code> (the reason is that this way I can use a <code>list</code> instead of a <code>dict</code> to access values associated to each combination, knowing the combination).</p>
  
  <p>Since <code>itertools</code> yields its combinations in a regular pattern it is possible to do it (and I also found a neat algorithm), but I'm looking for an even faster/natural way which I might ignore.</p>
  
  <p>By the way here is my solution:</p>
  
  <pre><code>def find_idx(comb,n):
      k=len(comb)
      idx=0
      last_c=0
      for c in comb:
          #idx+=sum(nck(n-2-x,k-1) for x in range(c-last_c-1)) # a little faster without nck caching
          idx+=nck(n-1,k)-nck(n-c+last_c,k) # more elegant (thanks to Ray), faster with nck caching
          n-=c-last_c
          k-=1
          last_c=c
      return idx
  </code></pre>
  
  <p>where <code>nck</code> returns the <a href="http://rosettacode.org/wiki/Evaluate_binomial_coefficients#Python" rel="nofollow">binomial coefficient of n,k</a>.</p>
  
  <p>For example:</p>
  
  <pre><code>comb=list(itertools.combinations(range(1,14),6))[654] #pick the 654th combination
  find_idx(comb,14) # -&gt; 654
  </code></pre>
  
  <p>And here is an equivalent but maybe less involved version (actually I derived the previous one from the following one). I considered the integers of the combination <code>c</code> as positions of 1s in a binary digit, I built a binary tree on parsing 0/1, and I found a regular pattern of index increments during parsing:</p>
  
  <pre><code>def find_idx(comb,n):
      k=len(comb)
      b=bin(sum(1&lt;&lt;(x-1) for x in comb))[2:]
      idx=0
      for s in b[::-1]:
          if s=='0':
              idx+=nck(n-2,k-1)
          else:
              k-=1
          n-=1
      return idx
  </code></pre>