时间戳

首页 > 解决方案 > Python - 所有组合，包括括号

python - Python - 所有组合，包括括号

问题描述

对于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

标签： pythonpython-3.xalgorithmitertools

解决方案

这一个会起作用，但它确实有很多表达方式，例如相同的事物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)

推荐阅读