Учитывая комбинациюk из первыхn натуральные числа, по какой-то причине мне нужно найти положение такой комбинации среди возвращенныхitertools.combination(range(1,n),k) (причина в том, что таким образом я могу использоватьlist вместоdict для доступа к значениям, связанным с каждой комбинацией, зная комбинацию).

посколькуitertools дает его комбинации в регулярном порядке, это можно сделать (и я также нашел аккуратный алгоритм), но я ищу еще более быстрый / естественный способ, который я мог бы игнорировать.

Кстати вот мое решение:

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

гдеnck возвращаетбиномиальный коэффициент n, k.

Например:

comb=list(itertools.combinations(range(1,14),6))[654] #pick the 654th combination
find_idx(comb,14) # -> 654

И вот эквивалентная, но, возможно, менее вовлеченная версия (на самом деле я вывел предыдущую из следующей). Я рассмотрел целые числа комбинацииc как позиции 1 в двоичной цифре, я построил двоичное дерево при разборе 0/1 и обнаружил регулярную последовательность приращений индекса при разборе:

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