生成字符串列表的所有组合，同时括号和操作符也被置换

Question

假设我有一个字符串列表：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中做过类似的事情，但它更容易，因为用户会构造实际的句子。它不是由一组排列和组合创建的。

Answer 1

您可以使用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']]

Answer 2

您可以使用生成器的递归：

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']]