StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFind the index of a given combination (of natural numbers) among those returned by `itertools` Python module
text
Body
copied!<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) # -> 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<<(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>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload