第七项

[hqztrue]

讲个鬼故事，考虑加减乘除，n=7的时候这个程序输出27906566，而OEIS: A140606上的第七项是27914126。(前六项都是一样的)

[MaigoAkisame]

你是跑了多久得到的结果呀？ 27906566 是 distinct expressions 还是 distinct values？

[hqztrue]

跑了几分钟吧。是distinct expressions。整个list我内存放不下，所以只用计数器统计了元素个数，应该是没有被我改坏的。(话说知乎这两天在维护... 本来想私信你的)

[MaigoAkisame]

我在公司的电脑上跑了10分钟复现了…… 这真的是个鬼故事……

[hqztrue]

我还拿c++翻译了一份用来当作我出的一个题的暴力对拍... 惨啊。换成c++之后n=8的时候只要跑3分钟就出来了

[MaigoAkisame]

我的结果还是少了而不是多了，这debug起来都难……

[hqztrue]

FYI, 我翻译的你的程序在n=8的时候输出1149129210。我先睡了...

[MaigoAkisame]

确实翻车了。

我的程序少生成了如下形式的算式： ((a - b) c + d - e) / (f - g) ((a - b) / c + d - e) / (f - g) (c / (a - b) + d - e) / (f - g) 这样的算式一共有 7! 3 = 15120 个，但通过调整正负号可以发现是两两成对等价的，所以其实只有 7560 个，正好等于 27914126 - 27906566。

粗略来说原因是这样的：最后一步除法，我是舍弃所有左子树为负极性的算式的。 但是，(a - b) c + d - e 跟它的相反数 (b - a) c + e - d，本应一正一负，但偏偏二者具有相同的形式。按我规定的赋予极性的方式，二者都成了负极性，这就造成了丢解。

我得仔细想一想怎么修复这个 bug，可能要大修……

[hqztrue]

hmmm这是个悲伤的故事。话说我试着凑过7560，发现分解质因数之后很好看，但没想明白那个多出来的3是个什么情况...

[MaigoAkisame]

先总结一下我到现在为止的思路，完全想通后再整理成专栏。

先捋清一些定义：

算式可以分为单项式和多项式。

• 单项式：只含一个字母的算式，或者最高层运算符为乘除的算式。例如 a, a * b, (a + b) / (c - d)。
• 多项式：最高层运算符为加减的算式。例如 a - b, a * b + c / d。

多项式去括号后，可以看成若干个单项式相加减。

算式的极性： 若一个算式可以通过交换其中若干个减号的被减数与减数，以及把其中若干个加号改为减号、减号改为加号而变成原式的相反数，则称算式有极性，否则称为无极性。 我在原专栏（https://zhuanlan.zhihu.com/p/34015231 ）中的定义叙述不完整，缺少了「加号改为减号、减号改为加号」的部分，不过程序中是按完整的定义来判断算式有无极性的。 有极性的算式是两两成对的，每对中的两个算式互为相反数。称其中任一者为正极性，另一者为负极性。 文章 https://zhuanlan.zhihu.com/p/34058293 指出，算式有极性等价于其中有减号，用数学归纳法不难证明。

算式的类型： 称一个算式为 k+p-m 型，如果它由 k 个有极性的单项式，加上 p 个无极性的单项式，减去 m 个无极性的单项式组成。

自然地：

• 合法算式不可能是 0+0-m 型，例如 -a, -a - b 都是不合法的。
• 无极性的单项式都是 0+1-0 型，例如 a, a * b。
• 无极性的多项式都是 0+p-0 型（p>1），例如 a + b。
• 有极性的单项式都是 1+0-0 型，例如 (a - b) / c。
• 有极性的多项式，k 和 m 中至少有一者大于 0。

有极性的单项式，其中至少含有 3 个字母。所以，一个 k+p-m 型的算式，其中至少含有 3*k+p+m 个字母。 有极性的多项式，至少含有 2 个字母，即 0+1-1 型，如 a - b。

算式类型的运算规则：

• 一个 K+P-M 型的算式与一个 k+p-m 型的算式相加，其结果为 (K+k)+(P+p)-(M+m) 型。
• 一个 K+P-M 型的算式与一个 k+p-m 型的算式相减，其结果为 (K+k)+(P+m)-(M+p) 型。
• 两个算式相乘除，得到的是单项式。若其中任一者有极性，则结果为 1+0-0 型；否则结果为 0+1-0 型。

一个 k+p-m 型（k>0）的算式（有极性），其相反数会是 k+m-p 型。 比如，一个 1+1-1 型的算式，其相反数也是 1+1-1 型的。 也就是说，算式的类型不能决定其极性的正负。 我翻车就是翻在这里：(a - b) c + d - e 跟它的相反数 (b - a) c + e - d，都是 1+1-1 型算式，它俩都被我的程序标记为负极性，而本来应该一正一负。 之所以到字母总数 n = 7 的时候才翻车，是因为翻车需要有一个 1+1-1 型算式与一个有极性的算式相除，前者至少需要 5 个字母，后者至少需要 2 个字母。

事实上，按照我程序中标记正负极性的规则，一个 k+p-m 型（k>0, m>0）算式的极性，必然会被标记成负极性。这是因为「无极性 - 有极性」、「有极性 - 有极性」的结果都是舍弃，所以 k+p-m 型算式只能由一个 k+p-0 型算式（有极性）减去一个 0+m-0 型算式（无极性）获得，而「有极性 - 无极性」的结果被标记为负极性。

要改正程序，就要修改算式极性的传播规则，至少要让 1+1-1 型算式的极性有正有负。 或者，就要完全绕开「极性」这个概念。

[hqztrue]

听起来有点麻烦，我有空想想。话说这个的计数版本不是已经被解决了么... 不知道是怎么做的

[MaigoAkisame]

计数版本见此：https://zhuanlan.zhihu.com/p/34058293 ，基本上就是递推。

我发现我的程序里，只要做如下的修改，结果就好像是正确的：

• 本来：有极性 + 无极性 = 正极性，有极性 - 无极性 = 负极性；
• 改为：有极性 +- 无极性 = 有极性者的极性。

这个修改的关键作用是，保证正、负极性的算式数目相同。

n = 7 的结果为：27,914,126 种表达式，其中无极性者有 2,345,072 种，正、负极性者各有 12,784,527 种； n = 8 正在跑，大约 2 小时后出结果。

不过话说回来，我觉得我没法证明修改后的规则就是正确的。 极性的运算法则太复杂、太丑陋了……

[hqztrue]

那个计数算法好像很麻烦吧(好吧我没仔细看)，真能像oeis上靖哲那样跑出三百项么？

[MaigoAkisame]

我也只看了理论，并没有研究编程实现……

[hqztrue]

我看你这个描述乱改了一下(其实我完全没有学习你的程序)，n=8跑出来是对的。C++还是快啊，我刷个牙的工夫就跑完了。

[MaigoAkisame]

哈哈，确实快！

[hqztrue]

接下来可以试试n=9... 我把我翻译的版本传上来？

[MaigoAkisame]

嗯好，可以开个 pull request。

[hqztrue]

等一下，我邮件发吧。怕被小朋友们发现当成暴力拿走...

[MaigoAkisame]

哈哈好~我的邮箱是 maigoakisame@gmail.com。

[hqztrue]

已发

[MaigoAkisame]

咦我还木有收到……

[hqztrue]

我新浪邮箱一向以来延迟比较高...

[MaigoAkisame]

收到啦~

[MaigoAkisame]

n=8 的结果出来了，是对的：总共 1,150,212,810 种表达式，其中无极性者有 68,652,032 种，正、负极性者各有 540,780,389 种。

[MaigoAkisame]

用你的 C++ 程序验证了 n=9 的情况：总共 54,326,011,414 种表达式，其中无极性者有 2,318,892,544 种，正、负极性者各有 26,003,559,435 种。

不过我还是不敢说修改后的程序就是正确的……

[hqztrue]

nice. 不过我也不知道怎么说明正确性...

[MaigoAkisame]

我把程序更新了。 告诉我一下你的知乎 id 呗，我在专栏里 at 你一下。

[MaigoAkisame]

git push --force 了好几下，不过最终的结果应该是干净的。

我把你的 C++ 程序大修了一下之后也放上来啦，小朋友们应该没法直接使用。