运算符和操作数的排列算法

Question

我在一个访谈网站上遇到了这个问题 - 我们给了4个数字说n1,n2,n3,n4.我们可以按任意顺序放置它们,我们可以在它们之间使用数学运算符+, - ,*,/来得到最终结果为24.为此编写一个算法 - 它将需要4个数字并返回false或true结果24可以任意组合.可以多次使用相同的运算符.

其中一种方法是 -

1. 置换运营商
2. 置换操作数
3. 将每个排列应用于2.中的每个排列.

这种解决方案是强力的,不是最佳解决方案.我认为使用二叉搜索树可能有更好的解决方案.

Answer 1

使用RPN(反向波兰表示法)

对于RPN介绍,请看这里.

问题的大小

我们必须建立一个包含4个运算符的四个数字的列表.
这些数字和运算符将被推送或执行堆栈.

让我们调用执行列表{a1 a2 a3 a4 a5 a6 a7}.

{a1 a2}应该是数字,因为堆栈上没有一元操作.

{a7}应该是操作员,以完成操作.

对于{a3,a4,a5,a6},我们有几个选项,但是堆栈中必须至少有两个数字才能运行.所以可能的组合是:(N =数,O =运算符)

{NNOO},{NONO},{ONON},{ONNO}和{NOON}.

禁止组合{OONN},因为第二个O的堆栈为空.

所以我们有:

      | {N N O O} |  
      | {N O N O} |  
{N N} | {O N O N} | {O}  
      | {O N N O} |  
      | {N O O N} |  

现在我们将计算可能的安排.当然,我们过度计算,因为可交换运算符(加号和时间)可以将排列树减少一半,但问题足够小,不必为此烦恼.(在序列为{OO}的情况下,我们也计算过多.但我们继续......)

我们必须为第一段选择四个数字,这是12种可能的安排.

对于中间段,剩下的两个数字可能只被置换,即因子2

但我们还有另一个因素5来计算中间段的五个替代品.

对于三个运营商,因为它们可能重复,我们有一个因子4 ^ 3 = 64

所以问题的大小是粗体数字的乘积:12 2 5 64 = 7680.不需要优化,我们可以通过蛮力继续进行.

问题的其余部分是建立7680安排和RPN评估员.两个相对容易的任务.

我会发布它...它仍然是一个草稿但是为时已晚!明天会跟着!

编辑:RPN评估员

这是递归RPN评估程序的代码.我选择用函数式语言(Mathematica)来简化操作符解析

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}

我们可以用它们代替元组中的vallues.例如:

  {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

当然,由于"加号"和"时代"的交换属性,其中许多都是微不足道的排列,但不是全部:

   {1, 2, Plus, 3, Plus, 4, Times}      -> ((1+2)+3)*4  = 24
   {2, 1, 4, 3, Times, Divide, Divide}  ->  2/(1/(4*3)) = 24

使用"Subtract"没有给出24的序列!

    In[260]:= MemberQ[Flatten@Select[t3, rpn[#] == 24 &], Subtract]
    Out[260]= False

结果谱样本