Генерация всех возможных «уникальных» выражений RPN (обратная польская запись)

Question

Я хочу генерировать в Python все возможные выражения RPN ( Обратная польская запись ), которые используют буквы из списка ввода (например, ['a', 'b', 'c']) и содержат операторы ['+', '-', '*', '/'].

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

Итак, я написал следующие функции:

1)

'''
The function returns True if we can add operator to current expression:
we scan the list and add +1 to counter when we meet a letter
and we add -1 when we meet an operator (it reduces
last two letters into 1 (say ab+ <--> a + b)
''' 
def can_add_operator(string_):
    n = 0
    for letter in string_:
        if letter not in ['+', '-', '*', '/']:
            n += 1
        else:
            n -= 1
    result = n > 1
    return result


    can_add_operator('ab*c+')) #False
    can_add_operator('ab*c')  #True

2)

'''
The function returns a list, that contains operators and
letters, one of which we can add to the current expression.
'''

def possible_elements(items, string_):
    #list of all letters that we have not used yet
    result =  [x for x in items if x not in string_]
    if can_add_operator(string_):
        result = ["+", "-", "*", "/"] + result
    return result

letters = ['a', 'b', 'c', 'd']
possible_elements(letters, 'ab*c') #['+', '-', '*', '/', 'd']
possible_elements(letters, '') #['a', 'b', 'c', 'd']
possible_elements(letters, 'ab*c+d+') #[]

3) Далее я заверну это в рекурсию:

#exp -- current expression, base of recursion is exp = ''
def rec(exp, Final_sol = []):
    elements_to_try = possible_elements(letters, exp)
    for i in elements_to_try:
        if len(possible_elements(letters, exp + i)) == 0:
            Final_sol.append(exp + i)
        else:
            rec(exp+i, Final_sol)
    return Final_sol

#we start with an empty string
Final_sol = rec('')
print(len(Final_sol)) #7680

Есть две сложности с этой функцией:

1. Во-первых, если в списке повторных букв письма, он не вернет все возможные результаты.

   Например, если letters = ['a', 'b', 'a']:

   Final_sol = rec('')
   print(len(Final_sol)) #32
   str(Final_sol)
   >> "['ab+', 'ab-', 'ab*', 'ab/', 'ba+', 'ba-', 'ba*', 'ba/', 'ba+', 'ba-', 
   'ba*', 'ba/', 'ab+', 'ab-', 'ab*', 'ab/', 'ab+', 'ab-', 'ab*', 'ab/', 'ba+', 
   'ba-', 'ba*', 'ba/', 'ba+', 'ba-', 'ba*', 'ba/', 'ab+', 'ab-', 'ab*', 
    'ab/']"
   

   Итак, на выходе отсутствует 'ab+a+' и так далее. Но я хочу вернуть все возможные комбинации в этом случае тоже.

2. Вторая проблема заключается в том, что в выход. Поскольку у нас есть коммутативные и ассоциативные свойства в префиксной форме, выражения вроде ab+c+ / abc++ / ca+b+ следует рассматривать как эквивалент: я хочу только одну из каждой группы в вывод функции rec ().

Как мы могли бы изменить функции выше, чтобы преодолеть такие трудности? Какое самое элегантное решение проблемы?

Answer 1

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

tree:                          *
                              / \
             +               -   c
            / \             / \
           a   b           a   b

infix:     a + b          (a - b) * c
postfix    a b +           a b - c *

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

Теперь, чтобы создать все возможные выражения, сначала нам понадобятся все структурно отличные полные двоичные деревья с len(operands) листьями или len(operands)-1 внутренними узлами.

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

Приведенный ниже код генерирует все структурно отличные полные двоичные деревья с n листьями.Он выводит древовидную структуру с некоторыми обозначениями, которые вы можете установить в функции.Он настроен на отображение поддеревьев в скобках, операндов как x и операторов как o.Например, для 2 операторов и 3 операндов:

(xo(xox))       ((xox)ox)
    o               o
   / \             / \
  x   o           o   x
     / \         / \
    x   x       x   x

from itertools import product

def expr_trees(n):
    if n == 1:
        yield 'x'

    for i in range(1, n):
        left = expr_trees(i)
        right = expr_trees(n-i)

        for l, r in product(left, right):
            yield '('+l+'o'+r+')'

for t in expr_trees(3):
    print(t)

Теперь, чтобы сгенерировать все возможные выражения, нам нужно поместить все перестановки без повторения операндов на листьях и все перестановки длины len(operands)-1 операторов с повторением на внутренних узлах каждой древовидной структуры.Здесь мы изменим функцию генератора, чтобы использовать список операторов и операндов и выходные выражения постфикса:

from itertools import permutations, product

def expressions(opds, oprs, idx):
    if len(opds) == 1:
        yield opds[0]

    for i in range(1, len(opds)):
        left = expressions(opds[0:i], oprs, idx+1)

        right = expressions(opds[i:], oprs, idx+1)

        for l, r in product(left, right):
            yield l+r+oprs[idx]

operands = ['a', 'b', 'c']
operators = ['+', '-', '*', '/']

operatorProducts = product(operators, repeat=len(operands)-1)
operandPermutations = permutations(operands)

for opds, oprs in product(operandPermutations, operatorProducts):
    for t in expressions(opds, oprs, 0):
        print(t)

Теперь о сложности времени.В качестве примера давайте вычислим количество всех структурно различных выражений для ['a', 'b', 'c'].

. Как мы видели ранее, существуют два полных двоичных дерева для трех операндов.Количество перестановок операндов равно 3! = 6, а число перестановок операторов равно 4^2, поскольку мы выбираем 2 из 4 с разрешенным повторением.Поэтому мы имеем:

number of expressions
    = number of trees * number of operand permutations * number of operator permutations
    = 2 * 6 * 16
    = 192

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

number of trees with n internal nodes = (1 / n+1) x (2n)! / (n! x n!)

Поэтому число структурно различных выражений с n операторами или n+1 операндами:

(n+1)! x 4^n x (1/n+1) x (2n)! / (n! x n!) = 4^n x (2n)! / n!

(извините за уродливые математические формулы из-за отсутствия поддержки. x - умножение. Вы можете найти более приятное форматирование по ссылкам выше.)

Обратите внимание, что n - это числовые операторыили число операндов - 1.

Как видите, число возможных выражений очень быстро растет с n.

1, 8, 192, 7680, 430080, 30965760, ...

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

Это подводит нас к следующей проблеме - поиску эквивалентных выражений.Поначалу это может показаться простым, поскольку можно подумать, что речь идет только о коммутативном свойстве + и *, но есть случаи, когда - и / изменяют остальную часть выражения сложными способами, которые трудно уловитьпросто простой RegExp, IMO.Например, abc-- эквивалентно ab-c+ из-за одинарного влияния минуса на элементы в скобках и более сложной версии с эффектом инверсии деления, abcde+-*/, что эквивалентно abcd-e-//.Добавление повторяющихся элементов в список операндов создает больше эквивалентных выражений и делает их еще труднее перехватить их все.

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

Answer 2

Во-первых, если в списке букв есть повторяющиеся буквы, он не вернет все возможные результаты.

Мы можем решить эту проблему, используя другой подход ксгенерируйте перестановки:

from itertools import permutations

variables = ['a', 'a', 'b', 'c']

operators = ['+', '-', '*', '/']

equations = set()

for permutation in permutations(variables):
    a, b, *rest = permutation

    operations = permutations(operators)

    for permutation in operations:

        equation = zip([a + b, *rest], permutation)

        equations.add("".join(variable + operator for variable, operator in equation))

Использование set() устранит любые дубликаты, вызванные повторяющимися переменными.

Вторая проблема заключается в том, что ввыход.Поскольку у нас есть коммутативные и ассоциативные свойства

Чтобы справиться с проблемой коммутативного , мы будем использовать сопоставление с образцом для сокращения уравнений:

import sys
import re

DEBUG = True

remove = set()

# Reduce commutative equivalents: ca*a-b/ same as ac*a-b/
if DEBUG:
    print("Reduce commutative equivalents:", file=sys.stderr)

for equation in equations:
    if equation not in remove:
        for match in re.finditer(r"(?=(.+)(\w)[+*])", equation):

            a, _ = match.span(1)
            _, d = match.span(2)

            equivalent = equation[:a] + match[2] + match[1] + equation[d:]

            if equivalent != equation and equivalent in equations:
                remove.add(equivalent)
                if DEBUG:
                    print(f"Removed {equivalent} same as {equation}", file=sys.stderr)

equations -= remove

Поскольку мы построили все уравнения как ab op c op d op и т. Д. Я не верю, что мы генерируем ассоциативные эквиваленты, но если бы мы это сделали, мы могли бы использовать аналогичную технику, чтобы попытаться их уменьшить:

remove = set()

# Reduce associative equivalents aa+b*c- same as ab*ab*+c-
if DEBUG:
    print("Reduce associative equivalents:", file=sys.stderr)

for equation in equations:
    if equation not in remove:
        for match in re.finditer(r"(?=(\w)([+])(\w)([*]))", equation):

            a, _ = match.span(1)
            _, d = match.span(4)

            equivalent = equation[:a] + match[3] + match[4] + match[1] + match[3] + match[4] + match[2] + equation[d:]

            if equivalent != equation and equivalent in equations:
                remove.add(equivalent)
                if DEBUG:
                    print(f"Removed {equivalent} same as {equation}", file=sys.stderr)

equations -= remove

И, наконец, выкинем наш сокращенный набор:

if DEBUG:
    print("Final equations:", file=sys.stderr)

print(equations)

ВЫХОД

> python3 test.py
Reduce commutative equivalents:
Removed ac+a-b/ same as ca+a-b/
Removed ab*a/c- same as ba*a/c-
Removed cb*a/a- same as bc*a/a-
Removed ac+b-a/ same as ca+b-a/
Removed ba+c/a- same as ab+c/a-
Removed ba+a-c/ same as ab+a-c/
Removed ac+a/b- same as ca+a/b-
Removed ac+b/a- same as ca+b/a-
Removed ac*b-a/ same as ca*b-a/
Removed bc*a-a/ same as cb*a-a/
Removed ca*a-b/ same as ac*a-b/
Removed ba*a-c/ same as ab*a-c/
Removed cb+a/a- same as bc+a/a-
Removed ba+c-a/ same as ab+c-a/
Removed ca*a/b- same as ac*a/b-
Removed ca*b/a- same as ac*b/a-
Removed ba+a/c- same as ab+a/c-
Removed ab*c-a/ same as ba*c-a/
Removed ab*c/a- same as ba*c/a-
Removed cb+a-a/ same as bc+a-a/
Reduce associative equivalents:
Final equations:
{'ca+a-b/', 'cb*a+a-', 'aa/b-c*', 'ba/c-a*', 'cb/a-a*', 'ab+a*c/', 'aa/c+b-',
'bc/a-a+', 'aa*b+c-', 'ba*a/c-', 'ab+c/a*', 'ca-a/b+', 'ca-b+a*', 'bc*a/a-',
'bc/a+a*', 'ac+a/b*', 'bc+a*a-', 'ca/a-b+', 'ac-a*b+', 'ba-a*c/', 'ac/b-a*',
'ba-c+a*', 'ba+a-c*', 'aa+b/c-', 'ca-b*a/', 'ca+b-a/', 'ab+c/a-', 'ac*b+a-',
'aa+c-b/', 'aa*c/b-', 'ab/c*a+', 'ac+b/a*', 'aa+b*c/', 'ab-a*c+', 'ac+a-b*',
'cb-a+a*', 'cb*a/a+', 'ab-c/a+', 'ac*b+a/', 'ba*c/a+', 'ba/c+a*', 'aa-b*c+',
'aa/b+c*', 'ab-c*a+', 'ac+a*b/', 'ac/b+a-', 'aa*b-c+', 'ac-a+b/', 'aa-c*b+',
'ab+a-c/', 'aa-c+b/', 'ba+c*a/', 'ca-b*a+', 'ab-a/c*', 'aa-b/c+', 'ac*a+b/',
'ba/a+c-', 'ba-c/a+', 'cb/a+a*', 'ca+b/a*', 'aa/c*b+', 'ac-a+b*', 'ba-a+c*',
'ca+a*b/', 'aa+b/c*', 'aa/c-b+', 'bc*a/a+', 'ca+a/b-', 'ca+b/a-', 'ca*b-a/',
'ac/b*a-', 'aa*b/c+', 'ba/a*c+', 'bc/a*a+', 'ca-b+a/', 'ac/b+a*', 'aa*b/c-',
'bc-a+a/', 'ca/b-a*', 'ba-c*a/', 'cb*a-a/', 'ba-c/a*', 'aa*b+c/', 'ac*a-b/',
'ca*b/a+', 'aa+b-c*', 'ba/a-c*', 'ca-b/a+', 'ab/c-a+', 'cb+a/a*', 'aa-c/b*',
'ba+c*a-', 'cb*a+a/', 'aa*c/b+', 'ab/c+a*', 'ca+b-a*', 'aa+b-c/', 'ac-b*a/',
'ab*a-c/', 'ba-a*c+', 'ba*c+a-', 'bc/a*a-', 'ba*c-a+', 'ba/c*a+', 'ab-c+a/',
'ba*c+a/', 'ca*a-b+', 'bc+a/a-', 'aa+c*b-', 'ab+c*a-', 'ac-a/b+', 'ca+a-b*',
'aa+c-b*', 'ab/c*a-', 'ab+c-a/', 'bc+a/a*', 'ac-a/b*', 'ab/a-c*', 'ac/a-b+',
'bc-a/a+', 'ab+a*c-', 'ac/a-b*', 'ca*a+b-', 'ab/a-c+', 'ab-a*c/', 'cb/a*a-',
'ac/a+b*', 'bc-a/a*', 'ac-b+a*', 'ac*a/b-', 'ba*a+c-', 'ba/a-c+', 'bc/a+a-',
'aa/b-c+', 'cb+a-a*', 'ca-b/a*', 'ca+b*a-', 'ac*b/a-', 'ca-a+b/', 'ca/b*a-',
'ba+a/c*', 'cb-a*a+', 'ac+a*b-', 'aa*b-c/', 'aa*c-b/', 'ac/a*b+', 'aa-c+b*',
'ca*a+b/', 'ca/b+a-', 'ac*a/b+', 'aa+c/b-', 'ab/c+a-', 'ab+a/c-', 'cb-a+a/',
'ab*a-c+', 'ab-a+c*', 'ab+a/c*', 'ac/b-a+', 'ab*c+a/', 'ba/c+a-', 'ba/c*a-',
'cb-a*a/', 'ac+b*a-', 'ba+c-a*', 'ac/b*a+', 'cb/a*a+', 'cb-a/a+', 'bc*a+a/',
'ac*b/a+', 'cb+a*a-', 'ba*c-a/', 'ca-a*b/', 'ca-a*b+', 'ab/a*c-', 'ba-a+c/',
'ba*a/c+', 'bc-a+a*', 'ca+a/b*', 'ca*a/b+', 'aa*c+b-', 'ba*c/a-', 'bc/a-a*',
'ca/a+b*', 'ab-a+c/', 'ca/b*a+', 'ab-a/c+', 'cb*a-a+', 'aa-b/c*', 'ac-b/a+',
'aa*c-b+', 'ab*c+a-', 'cb/a-a+', 'ab/a+c*', 'ba+a*c-', 'ba*a+c/', 'ba-a/c*',
'aa/b+c-', 'ba/c-a+', 'ca/b-a+', 'ab*a/c+', 'bc+a-a*', 'bc*a-a+', 'ab+c*a/',
'ab-c*a/', 'ac*a+b-', 'ca/a+b-', 'ac/a*b-', 'ac+b-a*', 'ba/a+c*', 'ba-a/c+',
'ab*c/a+', 'cb/a+a-', 'ca/a-b*', 'ac-b/a*', 'ab/a*c+', 'ca*b+a/', 'ac-a*b/',
'aa/b*c+', 'aa/c-b*', 'ca/a*b+', 'bc-a*a/', 'ca+b*a/', 'aa*c+b/', 'ab*a+c/',
'bc+a*a/', 'ab-c/a*', 'ca-a+b*', 'aa-c*b/', 'cb-a/a*', 'aa+b*c-', 'ca+a*b-',
'aa-b+c*', 'ac/a+b-', 'ba-c+a/', 'ba-c*a+', 'ca*b-a+', 'ac-b+a/', 'aa-b*c/',
'aa-b+c/', 'ac*a-b+', 'ac+b*a/', 'ca/a*b-', 'bc+a-a/', 'bc-a*a+', 'ba+a*c/',
'ac*b-a+', 'aa/c+b*', 'ab/a+c-', 'ab/c-a*', 'ab-c+a*', 'ba+c/a*', 'ab*c-a+',
'ab+a-c*', 'cb+a*a/', 'ac-b*a+', 'ba/a*c-', 'ab*a+c-', 'ab+c-a*', 'bc*a+a-',
'aa/b*c-', 'ca*b+a-', 'ba*a-c+', 'ca/b+a*', 'aa-c/b+', 'aa+c/b*', 'ca-a/b*',
'aa/c*b-', 'aa+c*b/'}
> 

Я не претендую на идеальное решение, просто иллюстрирую некоторыедоступных вам инструментов для решения вашей проблемы.