Сформировать сочетание его без генерации/итерации предыдущего

Question

Учитывая набор элементов, например:

[ 1, 2, 3, 4, 5, 6 ]

Я хотел бы, чтобы сгенерировать все возможные комбинации определенной длины с повторением. Твист - это то, что я хотел бы начать с предопределенной комбинации (своего рода смещение в список комбинаций).

Например, начиная с этого:

[ 1, 5, 6 ]

Первый (следующий) комбинация будет:

[ 1, 6, 6 ]

Я имел успех, используя itertools.combinations_with_replacement() для создания комбинаций, но для этого проекта требуется работа с набором, который генерирует слишком много комбинаций - создание их всех сначала и повторение в правильную точку невозможно.

Я нашел this example for generating kth combination, который, кажется, работает очень хорошо для меня. This answer казалась еще одной возможностью, но я не могу ее перенести с C на Python.

Вот мой код до сих пор с помощью kth combination example:

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 ] 

Любая помощь будет здорово!

Answer 1

Вместо того, чтобы изобрести колесо времени число 37,289,423,987,239,489,826,364,653 (который только подсчета люди), вы можете сопоставить числа. itertools вернет первую комбинацию [1,1,1], но вы хотите [1,5,6]. Просто добавьте [0,4,5] mod 6 в каждую позицию. Разумеется, вы также можете перемещаться между номерами, объектами и модулем.

Это работает, даже если количество элементов в каждой позиции различно.

У вас будет больше удовольствия с тем, что вы начали.

Answer 2

Если вы считаете, что все значения в массиве являются цифрами в системе нумерации base-n, где n - длина массива, k-я комбинация будет эквивалентна k, выраженной в base-n.

Если вы хотите начать с данной комбинации (т. Е. [1,6,5]) и продолжить оттуда, просто прочитайте эту начальную точку как число в base-n. Затем вы можете начинать итерацию с помощью последовательных комбинаций путем увеличения.

EDIT: Дальнейшее объяснение:

Давайте начнем с массивом. Массив содержит 6 значений, поэтому мы работаем в базе 6. Будем считать, что индекс каждого элемента в массиве является значением базового 6 элемента.

Значения в base-6 варьируются от 0 до 5. Это может ввести в заблуждение, потому что наш пример использует цифры, но мы могли бы сделать это с помощью комбинаций чего угодно. Я поставлю отметки «quote» вокруг цифр, которые мы объединяем.

Учитывая комбинацию ['1', '6', '5'], сначала нам нужно преобразовать ее в значение base-6. «1» становится равным 0, «6» становится равным 5, а «5» становится равным 4. Используя их позиции в стартовом значении в качестве их мощностей в базе-6, получаем:

(0 * 6^0) + (5 * 6^1) + (4 * 6^2) = 174 (десятичный)

Если мы хотим знать следующую комбинацию, мы можем добавить 1. Если мы хотим знать 20 комбинаций вперед, добавим 20. Мы также может вычесть назад.Давайте добавим 1 к 174 и преобразуем его обратно в base-6:

175 (десятичный) = (1 + 6^0) + (5 * 6^1) + (4 * 6^2) = 451 (базовый -6) = [ '2', '6', '5'] (сочетание)

более подробную информацию о числовых базах, см http://en.wikipedia.org/wiki/Radix и http://en.wikipedia.org/wiki/Base_%28exponentiation%29