Closed asukaminato0721 closed 4 years ago
做了些改动:
对照过 https://oeis.org/A140606 ,前 5 项都对,应该没改错。n=6 出的速度有点慢,放弃。
# -*- coding: utf-8 -*- # 结点类 from fractions import Fraction class Node: def __init__(self, ch=None, left=None, right=None, polar=0, id=0): self.ch = ch # 变量或运算符 self.left = left # 左孩子 self.right = right # 右孩子 self.polar = polar # 极性,可取 0, 1, -1 self.id = id # 结点编号 def __str__(self): # 把树转换成算式 if self.ch not in '+-*/': return self.ch # 单变量不加括号 left = str(self.left) # 左子树转字符串 right = str(self.right) # 右子树转字符串 if self.ch in '*/' and self.left.ch in '+-': left = '(' + left + ')' # 左子树加括号 if self.ch == '/' and self.right.ch in '+-*/' or self.ch in '*-' and self.right.ch in '+-': right = '(' + right + ')' # 右子树加括号 return left + ' ' + self.ch + ' ' + right # 用根结点的运算符相连 # 下面是几种 actions 函数,它们接收两个结点,返回它们的各种运算结果 # 「去重」者可以避免交换律、结合律、去括号、反转减号四种原因造成的重复 # 仅考虑加法与乘法,不去重 def naive2(left, right): for op in '+*': yield Node(op, left, right) yield Node(op, right, left) # 仅考虑加法与乘法,去重 def smart2(left, right): for op in '+*': if op != left.ch and (op != right.ch or left.id < right.left.id): yield Node(op, left, right) # 考虑加减乘除,不去重 def naive4(left, right): for op in '+-*/': yield Node(op, left, right) yield Node(op, right, left) # 考虑加减乘除,去重 def smart4(left, right): # 加法:两个孩子都不能是减号;左孩子还不能是加号; # 若右孩子是加号,则左孩子和右孩子的左孩子要满足单调性 if left.ch not in '+-' and right.ch != '-' and (right.ch != '+' or left.id < right.left.id): if left.polar == 0 or right.polar == 0: # 无极性 + 无极性 = 无极性 yield Node('+', left, right, left.polar + right.polar) # 有极性 + 无极性 = 有极性者的极性 else: # 有极性 + 有极性 = 右子树极性 yield Node('+', left, right, right.polar) # 减法:两个孩子都不能是减号 if left.ch != '-' and right.ch != '-': if left.polar == 0 and right.polar == 0: # 无极性 - 无极性: yield Node('-', left, right, 1) # 正过来减是正极性 yield Node('-', right, left, -1) # 反过来减是负极性 else: if left.polar == 0: # 有极性 - 无极性 = 有极性者的极性 yield Node('-', right, left, right.polar) # (无极性 - 有极性 = 舍弃) # (有极性 - 有极性 = 舍弃) if right.polar == 0: yield Node('-', left, right, left.polar) # 同上 # 乘法:两个孩子都不能是除号;左孩子还不能是乘号; # 若右孩子是乘号,则左孩子和右孩子的左孩子要满足单调性 if left.ch not in '*/' and right.ch != '/' and (right.ch != '*' or left.id < right.left.id): if left.polar == 0 or right.polar == 0: # 无极性 * 无极性 = 无极性 yield Node('*', left, right, left.polar + right.polar) # 有极性 * 无极性 = 有极性者的极性 elif left.polar > 0: # 正极性 * 有极性 = 右子树极性 yield Node('*', left, right, right.polar) # (负极性 * 有极性 = 舍弃) # 除法:两个孩子都不能是除号 if left.ch != '/' and right.ch != '/': if left.polar == 0 or right.polar == 0: # 无极性 / 无极性 = 无极性 yield Node('/', left, right, left.polar + right.polar) # 有极性 / 无极性 = 有极性者的极性 # 无极性 / 有极性 = 有极性者的极性 yield Node('/', right, left, left.polar + right.polar) # 同上 else: if left.polar > 0: # 正极性 / 有极性 = 右子树极性 yield Node('/', left, right, right.polar) # (负极性 / 有极性 = 舍弃) if right.polar > 0: yield Node('/', right, left, left.polar) # 同上 # 枚举由 n 个变量组成的算式 def enum(n, actions): def DFS(trees, minj): # trees 为当前算式列表,minj 为第二棵子树的最小下标 if len(trees) == 1: yield str(trees[0]) # 只剩一个算式,输出 return for j in range(minj, len(trees)): # 枚举第二棵子树 for i in range(j): # 枚举第一棵子树 for node in actions(trees[i], trees[j]): # 枚举运算符 node.id = trees[-1].id + 1 # 为新结点赋予 id new_trees = [treesk for k, treesk in enumerate( trees) if k != i and k != j] + [node] # 从列表中去掉两棵子树,并加入运算结果 new_minj = j - 1 if actions in (smart2, smart4) else 1 # 若 actions 函数去重,则此处也避免「独立运算顺序不唯一」造成的重复 for expression in DFS(new_trees, new_minj): # 递归下去 yield expression trees = [Node(chr(ord('a') + i), id=i) for i in range(n)] # 初始时有 n 个由单变量组成的算式 return DFS(trees, 1) def main(n): ''' >>> main(4) Expressions with only + and *: Smart: 52 expressions, 52 distinct expressions, 52 distinct values Naive: 1152 expressions, 528 distinct expressions, 52 distinct values Expressions with +, -, * and /: Smart: 1170 expressions, 1170 distinct expressions, 1170 distinct values Naive: 9216 expressions, 5856 distinct expressions, 1170 distinct values ''' # 给变量赋予一些随机数,用于统计不等价算式有多少个 global a, b, c, d, e, f, g, h a = Fraction(3141592) b = Fraction(6535897) c = Fraction(9323846) d = Fraction(2643383) e = Fraction(2795028) f = Fraction(8419716) g = Fraction(9399375) h = Fraction(1058209) # 仅考虑加法与乘法 print('Expressions with only + and *:') # 用去重的 actions 函数枚举算式 smart_exps = list(enum(n, smart2)) smart_uniq_exps = set(smart_exps) smart_uniq_values = set(eval(ex) for ex in smart_uniq_exps) print(f' Smart: {len(smart_exps)} expressions, {len(smart_uniq_exps)} distinct expressions, {len(smart_uniq_values)} distinct values') # 用不去重的 actions 函数枚举算式 naive_exps = list(enum(n, naive2)) naive_uniq_exps = set(naive_exps) naive_uniq_values = set(eval(ex) for ex in naive_uniq_exps) print(f' Naive: {len(naive_exps)} expressions, {len(naive_uniq_exps)} distinct expressions, {len(naive_uniq_values)} distinct values') # 考虑加减乘除 print('Expressions with +, -, * and /:') # 用去重的 actions 函数枚举算式 smart_exps = list(enum(n, smart4)) smart_uniq_exps = set(smart_exps) smart_uniq_values = set(eval(ex) for ex in smart_uniq_exps) print(f' Smart: {len(smart_exps)} expressions, {len(smart_uniq_exps)} distinct expressions, {len(smart_uniq_values)} distinct values') # 用不去重的 actions 函数枚举算式 naive_exps = list(enum(n, naive4)) naive_uniq_exps = set(naive_exps) naive_uniq_values = set(eval(ex) for ex in naive_uniq_exps) print(f' Naive: {len(naive_exps)} expressions, {len(naive_uniq_exps)} distinct expressions, {len(naive_uniq_values)} distinct values') if __name__ == "__main__": from doctest import testmod testmod() # 输入变量个数 n = int(input("输入变量个数: ")) # 主程序由此开始 main(n)
我还是交 pr 吧
做了些改动: