Ответ 1

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

Вы можете реализовать это рекурсивно каждый раз перед рекурсией, чтобы добавить другой элемент в комбинации, проверяя, будет ли это нарушать один из наборов исключений. Это не создает и недействительные комбинации и работает с перекрывающимися наборами исключений (например, (1,3), (1,5)) и исключает набор с более чем двумя элементами (например, (2,4,5), позволяя любые комбинации, за исключением всех их вместе).

def comb_with_excludes(lst, n, excludes, i=0, taken=()):
    if n == 0:
        yield taken  # no more needed
    elif i <= len(lst) - n:
        t2 = taken + (lst[i],)  # add current element
        if not any(e.issubset(t2) for e in excludes):
            yield from comb_with_excludes(lst, n-1, excludes, i+1, t2)
        if i < len(lst) - n:  # skip current element
            yield from comb_with_excludes(lst, n, excludes, i+1, taken)

Пример:

>>> lst = [1, 2, 3, 4, 5, 6]
>>> excludes = [{1, 3}, {1, 5}, {2, 4, 5}]
>>> list(comb_with_excludes(lst, 4, excludes))
[[1, 2, 4, 6], [2, 3, 4, 6], [2, 3, 5, 6], [3, 4, 5, 6]]

Ну, я сделал это сейчас, и получается, что это значительно медленнее, чем наивно, используя itertools.combination в выражении генератора с фильтром, как вы уже это делали:

def comb_naive(lst, r, excludes):
    return (comb for comb in itertools.combinations(lst, r)
                 if not any(e.issubset(comb) for e in excludes))

Вычисление комбинаций в Python происходит только медленнее, чем использование библиотеки (которая, вероятно, реализована на C), и фильтрация результатов впоследствии. В зависимости от количества комбинаций, которые могут быть исключены, в некоторых случаях это может быть быстрее, но, честно говоря, у меня есть сомнения.

Вы можете получить лучшие результаты, если вы можете использовать itertools.combinations для подзадач, как в ответе Kasramvd, но для нескольких, недискриминационных наборов исключений, которые сложнее. Одним из способов может быть разделение элементов в списке на два набора: те, которые имеют ограничения, и те, которые этого не делают. Затем используйте itertoolc.combinations для обоих, но проверьте ограничения только на комбинации тех элементов, где они имеют значение. Вам все равно придется проверять и фильтровать результаты, но только часть их. (Одно предупреждение: результаты не генерируются по порядку, а порядок элементов внутри полученных комбинаций также несколько испорчен).

def comb_with_excludes2(lst, n, excludes):
    wout_const = [x for x in lst if not any(x in e for e in excludes)]
    with_const = [x for x in lst if     any(x in e for e in excludes)]
    k_min, k_max = max(0, n - len(wout_const)), min(n, len(with_const))
    return (c1 + c2 for k in range(k_min, k_max)
                    for c1 in itertools.combinations(with_const, k)
                    if not any(e.issubset(c1) for e in excludes)
                    for c2 in itertools.combinations(wout_const, n - k))

Это уже намного лучше, чем рекурсивное решение pure-Python, но все же не так хорошо, как "наивный" подход для приведенного выше примера:

>>> lst = [1, 2, 3, 4, 5, 6]
>>> excludes = [{1, 3}, {1, 5}, {2, 4, 5}]
>>> %timeit list(comb_with_excludes(lst, 4, excludes))
10000 loops, best of 3: 42.3 µs per loop
>>> %timeit list(comb_with_excludes2(lst, 4, excludes))
10000 loops, best of 3: 22.6 µs per loop
>>> %timeit list(comb_naive(lst, 4, excludes))
10000 loops, best of 3: 16.4 µs per loop

Однако результаты во многом зависят от ввода. Для большего списка с ограничениями, применимыми только к некоторым из этих элементов, этот подход на самом деле быстрее, чем наивный:

>>> lst = list(range(20))
>>> %timeit list(comb_with_excludes(lst, 4, excludes))
10 loops, best of 3: 15.1 ms per loop
>>> %timeit list(comb_with_excludes2(lst, 4, excludes))
1000 loops, best of 3: 558 µs per loop
>>> %timeit list(comb_naive(lst, 4, excludes))
100 loops, best of 3: 5.9 ms per loop

Ответ 2

(Оказывается, это не делает то, что хочет OP. Все еще оставляя это здесь, поскольку это может помочь другим.)

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

>>> from itertools import combinations, product
>>> l = [[1, 3], [2], [4], [5]]
>>> [c for c in combinations(l, 4)]
[([1, 3], [2], [4], [5])]
>>> [p for c in combinations(l, 4) for p in product(*c)]
[(1, 2, 4, 5), (3, 2, 4, 5)]

Более сложный пример:

>>> l = [[1, 3], [2, 4, 5], [6], [7]]
>>> [c for c in combinations(l, 3)]
[([1, 3], [2, 4, 5], [6]),
 ([1, 3], [2, 4, 5], [7]),
 ([1, 3], [6], [7]),
 ([2, 4, 5], [6], [7])]
>>> [p for c in combinations(l, 3) for p in product(*c)]
[(1, 2, 6),
 (1, 4, 6),
 ... 13 more ...
 (4, 6, 7),
 (5, 6, 7)]

Это не создает никаких "нежелательных" комбинаций, которые впоследствии будут отфильтрованы. Тем не менее, предполагается, что вы хотите не более одного элемента из каждой "исключительной" группы, например, во втором примере, он не только предотвращает комбинации с 2,4,5, но также и с 2,4, 4,5 или 2,5. Кроме того, невозможно (или, по крайней мере, не легко) иметь исключительно один из 1,3 и 1,5, но разрешить 3,5. (Возможно, это возможно распространить на эти случаи, но я еще не уверен, что и как.)

Вы можете обернуть это в функцию, получив немного другой формат ввода из вашего (предполагаемого) формата и вернув выражающее выражение генератора. Здесь lst - это список элементов, r количество элементов для каждой комбинации и exclude_groups список групп взаимоисключающих элементов:

from itertools import combinations, product

def comb_with_excludes(lst, r, exclude_groups):
    ex_set = {e for es in exclude_groups for e in es}
    tmp = exclude_groups + [[x] for x in lst if x not in ex_set]
    return (p for c in combinations(tmp, r) for p in product(*c))

lst = [1, 2, 3, 4, 5, 6, 7]
excludes = [[1, 3], [2, 4, 5]]
for x in comb_with_excludes(lst, 3, excludes):
    print(x)

Ответ 3

С точки зрения алгоритма вы можете отделить исключенные и сбросить действительные элементы и рассчитать комбинации каждого набора отдельно и просто конкатенировать результат на основе длины желания. Этот подход полностью откажется от включения всех исключенных предметов одновременно в комбинации, но будет опускать фактический порядок.

from itertools import combinations

def comb_with_exclude(iterable, comb_num, excludes):
    iterable = tuple(iterable)
    ex_len = len(excludes)
    n = len(iterable)

    if comb_num < ex_len or comb_num > n:
        yield from combinations(iterable, comb_num)

    else:
        rest = [i for i in iterable if not i in excludes]
        ex_comb_rang = range(0, ex_len)
        rest_comb_range = range(comb_num, comb_num - ex_len, -1)
        # sum of these pairs is equal to the comb_num
        pairs = zip(ex_comb_rang, rest_comb_range)

        for i, j in pairs:
            for p in combinations(excludes, i):
                for k in combinations(rest, j):
                    yield k + p
       """
       Note that instead of those nested loops you could wrap the combinations within a product function like following:
       for p, k in product(combinations(excludes, i), combinations(rest, j)):
            yield k + p
       """

Демо-версия:

l = [1, 2, 3, 4, 5, 6, 7, 8]
ex = [2, 5, 6]
print(list(comb_with_exclude(l, 6, ex)))

[(1, 3, 4, 7, 8, 2), (1, 3, 4, 7, 8, 5), (1, 3, 4, 7, 8, 6), (1, 3, 4, 7, 2, 5), (1, 3, 4, 8, 2, 5), (1, 3, 7, 8, 2, 5), (1, 4, 7, 8, 2, 5), (3, 4, 7, 8, 2, 5), (1, 3, 4, 7, 2, 6), (1, 3, 4, 8, 2, 6), (1, 3, 7, 8, 2, 6), (1, 4, 7, 8, 2, 6), (3, 4, 7, 8, 2, 6), (1, 3, 4, 7, 5, 6), (1, 3, 4, 8, 5, 6), (1, 3, 7, 8, 5, 6), (1, 4, 7, 8, 5, 6), (3, 4, 7, 8, 5, 6)]

l = [1, 2, 3, 4, 5]
ex = [1, 3]
print(list(comb_with_exclude(l, 4, ex)))

[(2, 4, 5, 1), (2, 4, 5, 3)]

Benckmark с другими ответами:

Результаты: этот подход быстрее, чем другие

# this answer
In [169]: %timeit list(comb_with_exclude(lst, 3, excludes[0]))
100000 loops, best of 3: 6.47 µs per loop

# tobias_k
In [158]: %timeit list(comb_with_excludes(lst, 3, excludes))
100000 loops, best of 3: 13.1 µs per loop

# Vikas Damodar
In [166]: %timeit list(combinations_exc(lst, 3))
10000 loops, best of 3: 148 µs per loop

# mikuszefski
In [168]: %timeit list(sub_without(lst, 3, excludes[0]))
100000 loops, best of 3: 12.52 µs per loop

Ответ 4

Я попытался изменить комбинации в соответствии с вашими требованиями:

def combinations(iterable, r):
   # combinations('ABCD', 2) --> AB AC AD BC BD CD
   # combinations(range(4), 3) --> 012 013 023 123
   pool = tuple(iterable)
   n = len(pool)
   if r > n:
      return
   indices = list(range(r))
   # yield tuple(pool[i] for i in indices)
   while True:
       for i in reversed(range(r)):
           if indices[i] != i + n - r:
               break
    else:
        return
    indices[i] += 1
    for j in range(i+1, r):
        indices[j] = indices[j-1] + 1
    # print(tuple(pool[i] for i in indices ), "hai")
    if 1 in tuple(pool[i] for i in indices ) and 3  in tuple(pool[i] for i in indices ):
        pass
    else:
        yield tuple(pool[i] for i in indices)


d = combinations(list(range(1, 6)),4)
for i in d:
   print(i)

Он вернется примерно так:

(1, 2, 4, 5) (2, 3, 4, 5)

Ответ 5

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

обновление: рабочая скрипка

from itertools import permutations

def combinations(iterable, r, combIndeciesExclusions=set()):
    pool = tuple(iterable)
    n = len(pool)
    for indices in permutations(range(n), r):
        if ( len(combIndeciesExclusions)==0 or not combIndeciesExclusions.issubset(indices)) and sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)


l = list(range(1, 6))
comb = combinations(l, 4, set([0,2]))
print list(comb)

Ответ 6

Я думаю, что мой ответ похож на некоторых других здесь, но это было то, что я объединил параллельно

from itertools import combinations, product

"""
with help from
https://stackoverflow.com/questions/374626/how-can-i-find-all-the-subsets-of-a-set-with-exactly-n-elements
https://stackoverflow.com/questions/32438350/python-merging-two-lists-with-all-possible-permutations
https://stackoverflow.com/questions/952914/making-a-flat-list-out-of-list-of-lists-in-python
"""
def sub_without( S, m, forbidden ):
    out = []
    allowed = [ s for s in S if s not in forbidden ]
    N = len( allowed )
    for k in range( len( forbidden ) ):
        addon = [ list( x ) for x in combinations( forbidden, k) ]
        if N + k >= m:
            base = [ list( x ) for x in combinations( allowed, m - k ) ]
            leveltotal = [ [ item for sublist in x for item in sublist ] for x in product( base, addon ) ]
            out += leveltotal
    return out

val = sub_without( range(6), 4, [ 1, 3, 5 ] )

for x in val:
    print sorted(x)

>>
[0, 1, 2, 4]
[0, 2, 3, 4]
[0, 2, 4, 5]
[0, 1, 2, 3]
[0, 1, 2, 5]
[0, 2, 3, 5]
[0, 1, 3, 4]
[0, 1, 4, 5]
[0, 3, 4, 5]
[1, 2, 3, 4]
[1, 2, 4, 5]
[2, 3, 4, 5]

Ответ 7

Алгоритмически вы должны рассчитать комбинацию элементов в своем списке, которые не входят в число исключенных, затем добавить соответствующие комбинации исключенных элементов в комбинацию остальных элементов. Этот подход, конечно, требует большой проверки и необходимости отслеживать индексы, которые, даже если вы делаете это в python, не будут давать вам заметной разницы в производительности (известные как недостатки проблемы с ограничением ограничений). (а не просто вычислять их с помощью combination и фильтровать нежелательные элементы).

Поэтому я думаю, что это лучший способ пойти в большинстве случаев:

In [77]: from itertools import combinations, filterfalse

In [78]: list(filterfalse({1, 3}.issubset, combinations(l, 4)))
Out[78]: [(1, 2, 4, 5), (2, 3, 4, 5)]