Создание комбинаций из списка без учета смежных элементов - PullRequest
Новая
       14

Создание комбинаций из списка без учета смежных элементов

1 голос
/ 21 мая 2019

Я хочу генерировать комбинации из списка без учета смежных элементов.

Я пробовал код, который предоставляет комбинации без учета смежных элементов, и он работает с уникальными элементами в списке. Но это не работает с повторяющимися элементами в списке, например. [4,5,4,3]

Код: 

import itertools

b = []    
stuff = [4,5,4,3]

for L in range(2, len(stuff)+1):

    for subset in itertools.combinations(stuff, L):
        a =list(subset)       

        for i in range(1,len(a)):  

            if stuff.index(a[i-1]) == stuff.index(a[i])-1:

                a.clear()

                break

            else:

                b.append(a)

print('b = ',b)

Ожидаемый результат = [[4,4],[4,3],[5,3]]

Фактический результат = [[4, 4], [4, 3], [5, 4], [5, 3], [4, 3], [4, 4, 3], [4, 4, 3], [5, 4, 3], [5, 4, 3]]

Я могу объяснить на примере: предположим, что список [1,2,3,4,5], тогда возможные несмежные комбинации [[1,3], [1,4], [1,5], [2,4], [2,5], [3,5], [1,3,5]]. Я хочу эти комбинации. Код, который я пробую, хорошо работает с уникальным набором, но когда есть повторение чисел в данном списке, например [1,3,2,3,2,5], тогда при взятии индекса всегда берут первые 3, а не другие один. Так как же получить комбинации из этого набора

1 Ответ

1 голос
/ 22 мая 2019

Вместо того, чтобы генерировать все itertools.combinations и затем отфильтровывать действительные с помощью index, что (а) очень неэффективно и (б) не работает с дублирующимися элементами, вы должны реализовать свой собственный алгоритм combinations, что совсем не сложно, и может выглядеть примерно так: 

def comb(lst, num):
    if num == 0:
        yield []
    if 0 < num <= len(lst):
        first, *rest = lst
        for c in comb(rest, num-1):
            yield [first] + c
        for c in comb(rest, num):
            yield c

Чтобы добавить ограничение «нет смежных элементов», просто проследите, выбрали ли вы последний элемент, и добавьте толькоследующий элемент, если это не так: 

def comb_no_adj(lst, num, last=False):
    if num == 0:
        yield []
    if 0 < num <= len(lst):
        first, *rest = lst
        if not last:
            for c in comb_no_adj(rest, num-1, True):
                yield [first] + c
        for c in comb_no_adj(rest, num, False):
            yield c

Примером комбинаций для comb_no_adj([1,2,3,4,5,6], 3) являются [1, 3, 5], [1, 3, 6], [1, 4, 6], [2, 4, 6] (В этом примере не содержит дубликаты, просто для простотыпонять, поскольку этот алгоритм не использует index, дублирующиеся элементы не являются проблемой.)

Обновление: фактически сначала генерируются все комбинации, а затем отфильтровываются недопустимые комбинации. не может работать .Рассмотрим этот пример: [1,1,1].Все комбинации с двумя элементами будут [1,1], [1,1], [1,1] (первый и второй, первый и третий, а также второй и третий 1).Как бы вы решили, какие из них оставить, а какие выбросить?И это ухудшается для [1,1,1,1].(Вы могли бы сгенерировать все комбинации пар элементов-индексов и затем отфильтровать их, но из-за большого количества комбинаций, которые будут отфильтрованы в любом случае, это все равно будет менее эффективным.)

...