使用 RPN(逆波兰表示法)
有关 RPN 介绍,请参见here http://en.wikipedia.org/wiki/Reverse_Polish_notation.
问题大小
我们必须构建一个包含四个数字的列表,这意味着 3 个运算符。
这些数字和运算符将被推送到堆栈或在堆栈上执行。
让我们调用执行列表 {a1 a2 a3 a4 a5 a6 a7}。
{a1 a2} 应该是数字,因为堆栈上没有一元操作。
{a7}应该是一个运算符,完成运算。
对于 {a3, a4, a5, a6},我们有多种选择,但堆栈中必须至少有两个数字才能进行操作。所以可能的组合是:(N=数字,O=运算符)
{N N O O}、{N O N O}、{O N O N}、{O N N O} 和 {N O O N}。
组合 {O O N N} 被禁止,因为第二个 O 堆栈为空。
所以我们有:
| {N N O O} |
| {N O N O} |
{N N} | {O N O N} | {O}
| {O N N O} |
| {N O O N} |
现在我们来数一下可能的安排。当然,我们计算过多了,因为交换运算符(加号和乘号)可能会将排列树切成两半,但问题很小,不必为此烦恼。 (在序列为 {O O} 的情况下,我们也会计数过多。但我们只是继续下去..)
我们必须在 4 个数字中选择 2 个数字作为第一段,即12可能的安排。
对于中间段,剩下的两个数只能进行排列,即一个因子2
但我们还有另一个因素5用于计算中间部分的五种替代方案。
对于三个操作员,正如他们可能重复的那样,我们有一个因素4^3=64
所以问题的大小是粗体数字的乘积:12 2 5 64 = 7680。不需要优化,我们可以暴力破解。
剩下的问题是构建 7680 安排和 RPN 评估器。两项任务都相对简单。
我会发布它......它仍然是草稿,但为时已晚!明天继续!
编辑:RPN 评估器
下面是递归 RPN 求值器的代码。我选择用函数式语言来做(数学 http://www.wolfram.com/) 简化运算符解析
rpn[listipt_, stackipt_: {}] :=
Module[{list=listipt,stack=stackipt}, (*recursive rpn evaluator*)
If[list == {}, Return[stack[[1]]]]; (*end*)
If[NumberQ[list[[1]]], (*if numeric*)
Return@rpn[Rest[list], PrependTo[stack,list[[1]]]]; (*push nbr and recurse*)
,
(stack[[2]]=list[[1]][stack[[2]], stack[[1]]]; (*if not, operate*)
Return@rpn[Rest[list], Rest[stack]];); (*and recurse*)
];
];
使用示例
rpn[{1, 1, 1, Plus, Plus}]
3
rpn[{2, 2, 2, Plus, Plus}]
6
rpn[{2, 3, 4, Plus, Times}] (* (4+3)*7 *)
14
rpn[{2, 3, 4, Plus, Divide}] (* (2+3)/4 *)
2/7
稍后我将发布元组生成器,显示它们是 7680 以及一些关于操作可能结果的分布的有趣结果(事实上,对于 {1,2,3,4} 集,您只能得到 230不同的结果!)。
编辑:元组构造
首先我们明确构建中间部分的可能性
t1 = {{n3, n4, o1, o2},
{n3, o1, n4, o2},
{o1, n3, o2, n4},
{o1, n3, n4, o2},
{n3, o1, o2, n4}};
现在我们为 {n1,n2} 和最后一个运算符添加两个变体
t2 = Join[Map[Join[{n1, n2}, #, {o3}] &, t1],
Map[Join[{n2, n1}, #, {o3}] &, t1]] ( bahh ... don't mind the code*)
产生了 10 种不同的配置
现在我们必须用数字和运算符的所有可能排列来填充所有这些配置。
我们首先构造所有数字排列作为元组的分配规则
repListNumbers = (*construct all number permutations*)
Table[{n1 -> #[[1]], n2 -> #[[2]], n3 -> #[[3]], n4 -> #[[4]]} &[i],
{i, Permutations[{1, 2, 3, 4}]}];
这些小兽的形状
{n1 -> 1, n2 -> 2, n3 -> 3, n4 -> 4}
我们可以使用它们来替换元组中的值。例如:
{n1,n2,n3,o1,o2,n4,o3} /. {n1 -> 1, n2 -> 2, n3 -> 3, n4 -> 4}
结果是
{1,2,3,o1,o2,4,o3}
当然,我们可以将替换规则构建为一个函数,以便能够随意更改设置的数字。
我们现在对操作员做类似的事情
repListOps = (*Construct all possible 3 element tuples*)
Table[{o1 -> #[[1]], o2 -> #[[2]], o3 -> #[[3]]} &[i],
{i, Tuples[{Plus, Times, Divide, Subtract}, 3]}];
所以我们得到了诸如此类的集合
{o1->Plus, o2->Plus, o3->Divide}
现在我们将元组和所有替换规则合并到一个大列表中:
t3 = Flatten[t2 /. repListNumbers /. repListOps, 2];
这导致 15360 种不同的计算。但我们知道计算结果超出了两倍,所以现在我们删除重复的元素:
t3 =Union[t3]
这给了我们预期7680元素。
仍然存在一些计数过多的情况,因为 {2,3,Times} = {3,2,Times} = 6,但这对于我们当前的目的来说是可以的。
评估结果
现在我们有了 RPN 评估器和所有这些元组,我们想知道某个最终结果是否可能。
我们只需询问该数字是否包含在结果集中:
In[252]:= MemberQ[rpn /@ t3, 24]
Out[252]= True
In[253]:= MemberQ[rpn /@ t3, 38]
Out[253]= False
事实上,结果集的界限是:
In[254]:= Max[rpn /@ t3]
Out[254]= Max[36, ComplexInfinity]
In[255]:= Min[rpn /@ t3]
Out[255]= Min[-23, ComplexInfinity]
无穷大的结果是由于我不关心被零除的事实,所以它们就在那里,就在集合内。数字区间为[-23,36]。
如果你想知道有多少个结果等于 24,只需数一下即可
In[259]:= Length@Select[t3, rpn[#] == 24 &]
Out[259]= 484
当然,由于“Plus”和“Times”的交换性质,其中许多排列都是微不足道的排列,但并非全部:
{1, 2, Plus, 3, Plus, 4, Times} -> ((1+2)+3)*4 = 24
{2, 1, 4, 3, Times, Divide, Divide} -> 2/(1/(4*3)) = 24
没有任何序列使用“减法”给出 24!
In[260]:= MemberQ[Flatten@Select[t3, rpn[#] == 24 &], Subtract]
Out[260]= False
结果 光谱样本