枚举代数表达式的所有排列组合的算法。

Question

如果我有一个变量列表，比如{ }。A, B, C}和一个运算符列表，如{}。AND, 或}，如何才能有效地枚举所有有效表达式的排列组合？

鉴于上述情况，我希望看到的输出是（假设从左到右进行计算，没有运算符优先）。

• A AND B AND C
• A或B或C
• A和B或C
• A和C或B
• B和C或A
• A或B和C
• A或C和B
• B或C和A

我相信这是对所有输入组合的详尽列举。我不想多余，所以例如，我不会添加 "C OR B AND A"，因为这和 "B OR C AND A "是一样的。

有什么办法可以让我想出一个算法来做这件事吗？我真的不知道该从哪里开始。

Answer 1

递归是一个简单的选择。

void AllPossibilities(variables, operators, index, currentExpression){
    if(index == variables.size) {
        print(currentExpression);
        return;
    }
    foreach(v in variables){
        foreach(op in operators){
            AllPossibilities(variables, operators, index + 1, v + op);
        }
    }
}

Answer 2

这不是一个简单的问题 首先，你需要一个分组的概念，因为

(A AND B) OR C != A AND (B OR C)

其次，你需要生成所有的表达式。这将意味着迭代每一个术语的排列组合，以及排列组合中的术语分组。

第三，你必须实际解析每个表达式，将解析后的表达式带入一个规范的形式（比如说，CNF。https:/en.wikipedia.orgwikiBinary_expression_tree#Construction_of_an_expression_tree）。)

最后，你必须实际检查到目前为止看到的表达式的等价性。这就是检查解析形成的AST的等价性。

它看起来大致是这样的。

INPUT: terms
0. unique_expressions = empty_set
1. for p_t in permutations of terms:
2.   for p_o in permutations of operations:
3.     e = merge_into_expression(p_t, p_o)
4.     parsed_e = parse(e)
5.     already_seen = False
6.     for unique_e in unique_expressions:
7.       if equivalent(parsed_e, unique_e)
8.         already_seen = True
9.         break
10.    if not already_seen:
11.      unique_expressions.add(parsed_e)          

更多信息，请查看这篇文章。如何检查两个布尔表达式是否等价？