Python - все комбинации, включая скобки - PullRequest
Новая
       10

Python - все комбинации, включая скобки

0 голосов
/ 12 февраля 2019

Для u неизвестных переменных (например, a, b, c, d) и символов +-*/ найдите все возможные уравнения длины n

(for u=2, n=5):

(a + b) / a

Мой текущий код может создать список всех возможных уравнений, но без скобок 

v = ["a", "b"]            #Variables
s = ["+", "-", "*", "-"]  #Symbols
n = 7                     #Amount of variables and symbols
a = []                    #Lists combined (find possible equations from)
for i in range(n):
    if i % 2 == 0:
        a.append(v)
    else:
        a.append(s)
equations = list(itertools.product(*a))
for each in equations:
    print("".join(each))

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

Например, с n=5 and 2 variables мой код не может найти возможность (a+b)*b

С n=7 and 4 variables он не может найти `(a + b) * (c + d)

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

Пример дубликата: (a+b)*c и a*(b+c)

Примечание. Это дубликат, поскольку, поскольку каждое возможное уравнение проверяется, в некоторыхточка a+b станет b+c, поэтому *c станет *a

1 Ответ

0 голосов
/ 12 февраля 2019

Это сработает, но у него есть много выражений, которые приходят к одному и тому же, например, x-x или x/x с множеством разных вещей вместо x.Однако это позволяет избежать тривиальных дубликатов из-за ассоциативности или коммутативности.

Кроме того, список всех возможных выражений быстро становится безумно длинным.Например, с 4 переменными и всеми выражениями с 5 терминами, вы получите 7845320 из них.Использование генераторов защитит вас от нехватки памяти, но не заставит ее очень и очень долго работать. 

def all_expressions(size, variables):
    def _all_expressions(_size):
        if _size == 1:
            for variable in variables:
                yield (variable, '')
        else:
            for subsize in range(1, _size//2 + 1):
                for expr1, type1 in _all_expressions(subsize):
                    for expr2, type2 in _all_expressions(_size - subsize):
                        if subsize < _size - subsize or expr1 <= expr2:
                            if type1 == '+':
                                if type2 != '+':
                                    yield ("({} + {})".format(expr2, expr1), '+')
                            else:
                                yield ("({} + {})".format(expr1, expr2), '+')
                            if type1 == '*':
                                if type2 != '*':
                                    yield ("({} * {})".format(expr2, expr1), '*')
                            else:
                                yield ("({} * {})".format(expr1, expr2), '*')
                        if type1 != '*':
                            yield ("({} / {})".format(expr1, expr2), '/')
                        if type1 != '+':
                            yield ("({} - {})".format(expr1, expr2), '-')
                        if subsize < _size - subsize:
                            if type2 != '*':
                                yield ("({} / {})".format(expr2, expr1), '/')
                            if type2 != '+':
                                yield ("({} - {})".format(expr2, expr1), '-')
    for expr, t in _all_expressions(size):
        yield expr

for expr in all_expressions(3, ['a', 'b', 'c']):
    print(expr)
...