Существует очень эффективный алгоритм для этой проблемы, который также содержится в недавно опубликованной:Кнут, Искусство компьютерного программирования , том 4А (раздел 7.2.1.3).
Поскольку вас не волнует порядок, в котором создаются комбинации, давайте используем лексикографический порядокиз комбинаций, где каждая комбинация перечислена в порядке по убыванию .Таким образом, для r = 3 первые 11 комбинаций из 3 символов будут: 210, 310, 320, 321, 410, 420, 421, 430, 431, 432, 510. Преимущество этого порядка состоит в том, что перечисление не зависит отп;на самом деле это перечисление более всех комбинаций из 3 символов из {0, 1, 2,…}.
Существует стандартный метод для непосредственного генерации i th комбинация, заданная i, поэтому, чтобы проверить, является ли символ s частью i th комбинации, вы можете просто сгенерировать ее и проверить.
Метод
Сколько комбинаций r символов начинается с определенного символа s?Итак, оставшиеся позиции r-1 должны исходить из символов s 0, 1, 2,…, s-1, поэтому это (s выбирают r-1), где (s выбирают r-1) или C (s, r-1) - биномиальный коэффициент, обозначающий количество способов выбора объектов r-1 из s объектов.Поскольку это верно для всех s, первый символ i -ой комбинации является наименьшим s таким, что
∑ k = 0 s (k выберите r-1) ≥ i.
Как только вы узнаете первый символ, проблема сводится к нахождению (i - ∑ k = 0 s-1 (k выберите r-1)) - это комбинация символов r-1, где мы вычли те комбинации, которые начинаются с символа, меньшего s.
Код
Код Python (вы можете написать C(n,r) большеэффективно, но это достаточно быстро для нас):
#!/usr/bin/env python
tC = {}
def C(n,r):
if tC.has_key((n,r)): return tC[(n,r)]
if r>n-r: r=n-r
if r<0: return 0
if r==0: return 1
tC[(n,r)] = C(n-1,r) + C(n-1,r-1)
return tC[(n,r)]
def combination(r, k):
'''Finds the kth combination of r letters.'''
if r==0: return []
sum = 0
s = 0
while True:
if sum + C(s,r-1) < k:
sum += C(s,r-1)
s += 1
else:
return [s] + combination(r-1, k-sum)
def Func(N, r, i, s): return s in combination(r, i)
for i in range(1, 20): print combination(3, i)
print combination(500, 10000000000000000000000000000000000000000000000000000000000000000)
Обратите внимание, как быстро это:. он находит сочетание 10000000000000000000000000000000000000000000000000000000000000000th 500 букв (он начинается с 542) менее чем за 0,5 секунды