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

Question

我在一个面试网站上看到了这个问题—— 我们有 4 个数字，即 n1、n2、n3、n4。我们可以将它们放置在任何 顺序，我们可以在它们之间使用数学运算符 +、-、*、/ 最终结果为 24。为此编写一个算法 - 需要 4 个数字并返回 false 或 true 最终结果 24 是否可能 与任何组合。同一运算符可以多次使用。

实现此目的的方法之一是 -

1. 排列运算符 排列操作数
2. 将
3. 2 中的每个排列应用于 1 中的每个排列。

此解决方案将是强力解决方案，并且不是最佳解决方案。 我认为使用二叉搜索树可能有更好的解决方案。

Answer 1

使用 RPN（逆波兰表示法）

有关 RPN 介绍，请参阅此处。

问题大小

我们必须构建一个包含四个数字的列表，这意味着 3 个运算符。
这些数字和运算符将被压入堆栈或在堆栈中执行。

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

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

{a7}应该是一个运算符，完成运算。

对于 {a3, a4, a5, a6}，我们有多种选择，但堆栈中必须至少有两个数字才能进行操作。因此，可能的组合是：（N= 数字，O=操作员）

{NNOO}、{NONO}、{ONON}、{ONNO} 和 {NOON}。

组合 {OONN} 是被禁止的，因为第二个 O 的堆栈是空的。

所以我们有：

<前> <代码> | {NNOO} |
| {诺诺} |
{NN} | {ONON} | {O}
| {ONNO} |
| {中午}|

现在我们来数一下可能的安排。当然，我们计算过多了，因为交换运算符（加号和乘号）可能会将排列树切成两半，但问题很小，不必为此烦恼。 （在序列为 {OO} 的情况下，我们也会计数过多。但我们只是继续下去..）

我们必须在第一段的 4 个数字中选择 2 个数字，即 12 种可能的排列。

对于中间段，剩下的两个数字只能进行排列，即因子2，

但是我们还有另一个因子5来计算中间段的五个替代方案。

对于三个运算符，因为它们可能重复，所以我们有一个因子 4^3=64

因此，问题的大小是粗体数字的乘积：12 2 5 64 = 7680< /b>.不需要优化，我们可以暴力破解。

剩下的问题是构建 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}

我们可以使用它们来替换元组中的值。例如：

  {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

结果 频谱示例