Алгоритм перечисления всех перестановок алгебр c выражений

Question

Если у меня есть список переменных, например { A , B , C}, и список операторов, например { AND , OR }, как я могу эффективно перечислить все перестановки допустимых выражений? вправо без приоритета операторов):

• A AND B AND C
• A OR B OR C
• A AND B OR C
• A AND C OR B
• B AND C OR A
• A OR B AND C
• A OR C AND B
• B OR C AND A

Я считаю, что это исчерпывающий перечень всех комбинаций входных данных. Я не хочу быть лишним, поэтому, например, я бы не стал добавлять «C OR B AND A», потому что это то же самое, что «B OR C AND A».

Any идеи, как я могу придумать алгоритм для этого? Понятия не имею, с чего начать.

Answer 1

Это непростая проблема. Во-первых, вам нужно понятие группировки, потому что

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

Во-вторых, вам нужно сгенерировать все выражения. Это будет означать повторение каждой перестановки терминов и группирование терминов в перестановке.

В-третьих, вы должны фактически проанализировать каждое выражение, приведя проанализированные выражения в каноническую форму (скажем, CNF. https://en.wikipedia.org/wiki/Binary_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)          

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

Answer 2

Рекурсия - это простой вариант go:

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);
        }
    }
}