Генерация всех комбинаций из 2 списков (игра в игру) - PullRequest
Новая
       6

Генерация всех комбинаций из 2 списков (игра в игру)

0 голосов
/ 19 октября 2018

Я пытаюсь сгенерировать все возможные комбинации между 2 списками A и B в python с несколькими ограничениями.A и B чередуются в значениях выбора, A всегда выбирает первым.А и В могут иметь перекрывающиеся значения.Если A уже выбрал значение, то B не может выбрать его, и наоборот.

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

Также элементы, выбранные каждым, должны быть в порядке возрастания, то есть A[1] < A[2] < .... A[n] и B[1] < B[2] < .... B[n], где A[i] и B[i] - этоi -й элемент, выбранный A и B соответственно

Пример: 

A = [1, 2, 3, 4]
B = [2, 5]

Нужное решение: 

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

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

На данный момент, это то, как я решаю это: 

A = [1, 2, 3, 4]
B = [2, 5]
A_set = set(A)
B_set = set(b)
#Append both sets
C = A.union(B)
for L in range(len(C), 0, -1):
        for subset in itertools.combinations(C, L):
        #Check if subset meets constraints and print it if it does

1 Ответ

0 голосов
/ 19 октября 2018

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

Примерно так (это можно улучшить, добавив параметры для текущего индекса в оба списка вместо того, чтобы фактически разрезать списки для рекурсивных вызовов): 

def solve(n, lst1, lst2, selected):
    if n == 0:
        yield []
    elif lst1:
        for i, x in enumerate(lst1):
            if x not in selected:
                selected.add(x)
                for rest in solve(n-1, lst2, lst1[i+1:], selected):
                    yield [x] + rest
                selected.remove(x)

Или немногоболее сжатый: 

def solve(n, lst1, lst2, selected):
    if n == 0:
        yield []
    elif lst1:
        yield from ([x] + rest for i, x in enumerate(lst1) if x not in selected
                               for rest in solve(n-1, lst2, lst1[i+1:], selected.union({x})))

Пример: 

A = [1, 2, 3, 4]
B = [2, 5]
result = [res for n in range(1, len(A)+len(B)+1) for res in solve(n, A, B, set())]

Впоследствии result это: 

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