Я использую алгоритм «звездочки и столбцы» для выбора элементов из нескольких списков, причем количество звездочек между столбцами k и k + 1 является индексом в k-м списке.Проблема, с которой я сталкиваюсь, состоит в том, что разделы (то есть количество звездочек между двумя столбцами) могут быть больше, чем размер списка, что приведет к множеству недопустимых комбинаций.
Например: если у меня есть два списка длиной 8, (14,0) является действительным распределением звезд для суммы = 14, но, конечно, превысит емкость первого списка.(7,7) - это самый высокий допустимый индекс, поэтому я получаю большое количество недопустимых индексов, особенно если списки не имеют одинаковый размер.
Из соображений производительности мне нужен вариант алгоритма с ограниченным размером раздела.Как я могу это сделать?Реализация звездочек и полосок, которую я сейчас использую, - , , но я легко могу ее изменить.Списки обычно имеют одинаковую длину, но не обязательно одинаковой длины.Я согласен с ограничением размеров разделов до длины самого длинного списка, но отдельные ограничения, конечно, будут лучше.
import itertools
def stars_and_bars(stars, partitions):
for c in itertools.combinations(range(stars+partitions-1), partitions-1):
yield tuple(right-left-1 for left,right in zip((-1,) + c, c + (stars+partitions-1,)))
def get_items(*args):
hits = 0
misses = 0
tries = 0
max_idx = sum(len(a) - 1 for a in args)
for dist in range(max_idx):
for indices in stars_and_bars(dist, len(args)):
try:
tries += 1
[arg[i] for arg,i in zip(args,indices)]
hits += 1
except IndexError:
misses += 1
continue
print('hits/misses/tries: {}/{}/{}'.format(hits, misses, tries))
# Generate 4 lists of length 1..4
lists = [[None]*(r+1) for r in range(4)]
get_items(*lists)
# hits/misses/tries: 23/103/126
Редактировать : я нашел два связанных вопроса по mathexchange, но я пока не смог перевести их в код: