Генерация всех комбинаций списка строк с круглыми скобками и переставляемым оператором - PullRequest
Новая
       95

Генерация всех комбинаций списка строк с круглыми скобками и переставляемым оператором

3 голосов
/ 29 марта 2019

Допустим, у меня есть список строк: l = ['A','B','C','D']

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

Например, list(combinations(l, 2)) даст мне

[['A','B'], ['A','C'],['A','D'],['B','C'],['B','D'],['C','D']]

Однако вместо скобок мне бы хотелось скобки:

['(A,B)', '(A,C)','(A,D)','(B,C)','(B,D)','(C,D)']

Теперь, скажем, я хочу расширить это и добавить две операции для этих AND и OR:

, чтобы я получил ['(A','AND','B)', '(A','OR','B)',etc.]

Продлите это еще дальше, чтобы получить вложенные скобки в случае, если n=3: 

['((A','AND','B)', 'AND', 'C)', '((A','AND','B)', 'OR', 'C)', '((A','OR','B)', 'OR', 'C)', '((A','OR','B)', 'AND', 'C)', etc.]

С ним в идеале, имеющим форму: 

['((A AND B) AND C)', '((A AND B) OR C)', '((A OR B) OR C)', '((A OR B) AND C)', etc.]

Итак, в итоге,Я выбираю комбинации из списка n элементов за раз, с перестановками операторов ['AND', 'OR'] и добавляю вложение слева.

Я сделал нечто подобное в JavaScript, нотам было проще, так как пользователь построит реальное предложение.Он не был создан из набора перестановок и комбинаций.

Ответы [ 2 ]

2 голосов
/ 30 марта 2019

Вы можете использовать itertools.combinations, чтобы выбрать операнды из данного списка, использовать itertools.product, чтобы создать комбинации операторов, и снова использовать itertools.product, чтобы создать все смеси операндов и операторов, и использовать цикл for, которыйсохраняет вложенные списки в соответствии с выбранными операндами и операторами для создания желаемого результата: 

from itertools import combinations, product
def expressions(l, n):
    for (operations, *operands), operators in product(
            combinations(l, n), product(('AND', 'OR'), repeat=n - 1)):
        for operation in zip(operators, operands):
            operations = [operations, *operation]
        yield operations

, так что list(expressions(['A','B','C','D'], 3)) возвращает: 

[[['A', 'AND', 'B'], 'AND', 'C'],
 [['A', 'AND', 'B'], 'OR', 'C'],
 [['A', 'OR', 'B'], 'AND', 'C'],
 [['A', 'OR', 'B'], 'OR', 'C'],
 [['A', 'AND', 'B'], 'AND', 'D'],
 [['A', 'AND', 'B'], 'OR', 'D'],
 [['A', 'OR', 'B'], 'AND', 'D'],
 [['A', 'OR', 'B'], 'OR', 'D'],
 [['A', 'AND', 'C'], 'AND', 'D'],
 [['A', 'AND', 'C'], 'OR', 'D'],
 [['A', 'OR', 'C'], 'AND', 'D'],
 [['A', 'OR', 'C'], 'OR', 'D'],
 [['B', 'AND', 'C'], 'AND', 'D'],
 [['B', 'AND', 'C'], 'OR', 'D'],
 [['B', 'OR', 'C'], 'AND', 'D'],
 [['B', 'OR', 'C'], 'OR', 'D']]
2 голосов
/ 29 марта 2019

Вы можете использовать рекурсию с генератором: 

def op(d, n, _d, c = []):
  if _d == 1:
    yield c
  else:
    for i in d:
      if sum(isinstance(h, list) or h not in {'AND', 'OR'} for h in c) == n:
         yield from op(d, n, _d-1, c=[c, 'OR', i])
         yield from op(d, n, _d-1, c=[c, 'AND', i])
      else:
         if not c:
           yield from op(d, n, _d, c=[i])
         else:
           yield from op(d, n, _d, c=[*c, 'OR', i])
           yield from op(d, n, _d, c=[*c, 'AND', i])

result = list(op(['A','B','C','D'], 2, 2))

Выход (первые десять результатов): 

[[['A', 'OR', 'A'], 'OR', 'A'], [['A', 'OR', 'A'], 'AND', 'A'], [['A', 'OR', 'A'], 'OR', 'B'], [['A', 'OR', 'A'], 'AND', 'B'], [['A', 'OR', 'A'], 'OR', 'C'], [['A', 'OR', 'A'], 'AND', 'C'], [['A', 'OR', 'A'], 'OR', 'D'], [['A', 'OR', 'A'], 'AND', 'D'], [['A', 'AND', 'A'], 'OR', 'A'], [['A', 'AND', 'A'], 'AND', 'A']]

Это решение позволит вам контролировать длину и глубину каждогоэлемент в result.Например, при генерации на глубину 4: 

result = list(op(['A','B','C','D'], 2, 4))
print(result[:10])

Вывод: 

[[[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'AND', 'A'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'OR', 'B'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'AND', 'B'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'OR', 'C'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'AND', 'C'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'OR', 'D'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'AND', 'D'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'AND', 'A'], 'OR', 'A'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'AND', 'A'], 'AND', 'A']]
...