Дан набор предметов, например:
[ 1, 2, 3, 4, 5, 6 ]
Я хочу сгенерировать все возможные комбинации определенной длины с повторением. Суть в том, что я хотел бы начать с заранее определенной комбинации (своего рода смещения в списке комбинаций).
Например, начиная с этого:
[ 1, 5, 6 ]
Первая (следующая) комбинация будет:
[ 1, 6, 6 ]
Я успешно использовал itertools.combinations_with_replacement() для генерации комбинаций, но проект, для которого он предназначен, потребует работы с набором, который генерирует слишком много комбинаций - создание их всех в первую очередь и повторение до нужной точки невозможно.
Я нашел этот пример для генерации k-й комбинации, которая, похоже, у меня не очень хорошо работает. Этот ответ казался другой возможностью, но я не могу перенести его с C на Python.
Вот мой код с использованием k-го примера комбинации:
import operator as op
items = [ 1,2,3,4,5,6 ]
# https://stackoverflow.com/a/4941932/1167783
def nCr(n, r):
r = min(r, n-r)
if r == 0:
return 1
numer = reduce(op.mul, xrange(n, n-r, -1))
denom = reduce(op.mul, xrange(1, r+1))
return numer // denom
# https://stackoverflow.com/a/1776884/1167783
def kthCombination(k, l, r):
if r == 0:
return []
elif len(l) == r:
return l
else:
i = nCr(len(l)-1, r-1)
if k < i:
return l[0:1] + kthCombination(k, l[1:], r-1)
else:
return kthCombination(k-i, l[1:], r)
# get 1st combination of 3 values from list 'items'
print kthCombination(1, items, 3)
# returns [ 1, 2, 4 ]
Любая помощь была бы замечательной!
