算法运算符和操作数的排列 [英] Algorithm for permutations of operators and operands
问题描述
我碰到在接受记者采访时网站这个问题 - 我们得到4号说N1，N2，N3，N4。我们可以将它们放置在任何 为了我们可以用数学运算符+， - 中，*，/他们之间 有最后的结果是24，写一个算法，这一点 - 它会 4号和返回，假意或真心最终结果24是否可能 用任何组合。相同的操作者可多次使用。
其中一个方法可以做到这将是的 -
- 置换运营商
- 置换的操作数
- 申请，每次改变2.每次改变1。
该解决方案将是暴力破解，也不会是最佳解决方案。 我觉得可能是用二叉搜索树一个更好的解决方案。
使用RPN（逆波兰式）
有关RPN介绍请参见这里。
问题的大小
我们要建立四个数字，这意味着3个操作员的名单。
这些数字和运算符将被推或对堆栈执行。
让我们称之为执行{A1 A2 A3 A4 A5 A6 A7}的列表。
{A1 + A2}必须是数字，因为没有一元运算栈上。
{A7}应该是一个经营者，完成操作。
有关{A3，A4，A5，A6}我们有几种选择，但总是至少两个数必须在堆栈能够操作。因此，可能的组合有：（N =数字，O =操作员）
{NNOO}，{NONO}，{ONON}，{ONNO}和{}正午。
结合{} OONN是被禁止的，因为堆栈是空的第二个O操作。
因此，我们有：
| {N N 2 O O} | | {N 2 O N 2 O} | {N N} | {0：N 0：N} | {O} | {0：N N 2 O} | | {N○○N} |
现在，我们将计算可能的安排。当然，我们在计算，因为可交换操作（Plus和时间）可能下调的排列树的一半，但问题是小到不会被打扰。 （我们还超量在这些情况下的序列{} OO。但我们只是去..）
我们必须选择2号在四为第一段，这是 12 的可能安排。
有关的中间段，其余的两个数字可仅被排列，这是一个因素的 2 的
但是，我们有另外一个因素 5 以计数的五个备选方案的中间段。
有关三大运营商，因为它们可能会重复，我们有一个系数 4 ^ 3 = 64
所以问题的大小的数字以粗体产物：12 2 5 64 =的 7680 的。没有优化是必要的，我们可以用蛮力继续前进。
问题的其余部分是建立在7680安排和RPN评估。这两个相对简单的任务。
我会后它...它仍然是一个草案，但这里是为时已晚！将遵循明天！
编辑：RPN计算器
下面是code的递归RPN计算器。我选择做一个功能性的语言（数学），以简化操作解析
RPN [listipt_，stackipt_：{}]：=
模块[{列表= listipt，堆栈= stackipt}，（*递归RPN计算器*）
如果[列表== {}，回车[堆栈[[1]]]]; （*结束*）
如果[NumberQ [列表[[1]]]，（*如果数值*）
返回@ RPN [休息[名单]，prependTo [堆栈，列表[[1]]]]; （*推NBR和递归*）
，
（堆叠[[2]] =列表[[1]] [堆叠[[2]]，堆叠[[1]]];（如果不是*，操作*）
返回@ RPN [休息[名单]，休息[堆栈]]）; （*和递归*）
]。
]。
使用示例
RPN [{1，1，1，加，加}]
3
RPN [{2,2，2，另外，加}]
6
RPN [{2，3，4，另外，时报}]（*（4 + 3）* 7 *）
14
RPN [{2，3，4，另外，分割}]（*（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}};
现在我们prePEND的两个版本的{N1，N2}最后运营商
T2 =加入[地图[加入[{N1，N2}，＃{} O3]放大器;，T1]
地图[加入[{N2，N1}＃{O3}]放大器;，T1]（bahh ......不介意code *）
导致我们的10个不同的配置
现在我们来填充所有这些配置与数字和运算的所有可能的排列。
我们首先构建所有的数字排列的分配规则我们的元组
repListNumbers =（*构造所有号码排列*）
表[{N1 - ＆GT; ＃[[1]]，N2 - ＆GT; ＃[[2]]，N3 - ＆GT; ＃[[3]]，N4 - ＆GT; ＃[[4]}＆安培; [I]中，
{I，置换[{1，2，3，4}]}];
这些小兽的格式
{N1 - ＆GT; 1，N2 - ＆GT; 2，N3 - ＆GT; 3，N4 - ＆GT; 4}
我们可以用它们来代替vallues在我们的元组。例如：
{N1，N2，N3，O1，O2，N4，O3} /。 {N1 - ＆GT; 1，N2 - ＆GT; 2，N3 - ＆GT; 3，N4 - ＆GT; 4}
结果在
{1,2,3，01，o2,4，O3}
当然，我们可能已构建了置换规则的函数，以便能够改变设定随意的数目。 我们现在做同样的事情与运营商合作
repListOps =（*构造所有可能的3元的元组*）
表[{01 - ＆GT; ＃[[1]]，O 2 - ＆GT; ＃[[2]]，O3 - ＆GT; ＃[[3]]}＆安培; [I]中，
{我，元组[{另外，时代，分割，减}，3]}];
所以，我们得到的东西的集合像
{o1-＆GT;另外，O2-＆GT;另外，O3-＆GT;分割}
现在我们结合我们的元组和我们所有的替换规则在一个大名单：
T3 =拼合[T2 /。 repListNumbers /。 repListOps，2];
这将导致15360不同的计算。但是，我们知道，有高估的二分之一，所以现在我们删除重复的元素：
T3 =联盟[T3]
这给我们我们预期的 7680 元素。
还有一些超量，因为{2,3，次} = {3,2，次} = 6，但是这是确定我们目前的效果影响不大。
评估的结果
现在，我们有我们的RPN评估和所有元组，我们想知道，如果某最终的结果是可能的。
我们只是要问，如果这个数字包含在结果集：
在[252]：= MemberQ [RPN / @ T3，24]
出[252] = TRUE
在[253]：= MemberQ [RPN / @ T3，38]
出[253] = FALSE
在事实上的边界，该结果集是：
在[254]：=最大值[RPN / @ T3]
出[254] =最大值[36，ComplexInfinity]
在[255]：=最小值[RPN / @ T3]
出[255] =最小值[-23，ComplexInfinity]
无穷大的结果是由于这样的事实，我没有通过零在乎师，让他们在那里，只是里面的设置。该数值区间为[-23,36]。
如果你想知道结果如何了许多等于24，仅仅指望他们
在[259]：=长度@选择[T3，RPN [＃] == 24安培]
出[259] = 484
当然，其中不少是微不足道的排列由于加和泰晤士报的可交换性，但不是所有的：
{1，2，另外，3，另外，4，时代} - ＆GT; （（1 + 2）3）* 4 = 24
{2，1，4，3，时代，分割，分割} - ＆GT; 2 /（1 /（4 * 3））= 24
还有用减法，让24是没有顺序！
在[260]：= MemberQ [拼合@选择[T3，RPN [＃] == 24安培]，减]
出[260] = FALSE
结果频谱采样
I came across this question on an interview website - We are given 4 numbers say n1, n2, n3, n4. We can place them in any order and we can use the mathematical operators +, -, *, / in between them to have the final result as 24. Write an algorithm for this - it will take 4 numbers and return false or true whether final result 24 is possible with any combination. The same operator can be used multiple times.
One of the ways to do this would be to -
- Permute the operators
- Permute the operands
- Apply every permutation in 2. to every permutation in 1.
This solution would be brute force and would not be an optimal solution. I think there might be a better solution using binary search trees.
Using RPN (reverse Polish Notation)
For RPN intro see here.
The Problem size
We have to build a list of four numbers, which implies 3 operators.
Those numbers and operators will be pushed or executed against a stack.
Lets call the list of execution {a1 a2 a3 a4 a5 a6 a7}.
{a1 a2} should be numbers, as there are no unary operations on the stack.
{a7} should be an operator, to complete the operation.
For {a3, a4, a5, a6} we have several options, but always at least two numbers must be in the stack to be able to operate. So the possible combinations are: (N= number, O=Operator)
{N N O O}, {N O N O}, {O N O N}, {O N N O} and {N O O N}.
The combination {O O N N} is forbidden because the stack is empty for the second O.
So we have:
| {N N O O} | | {N O N O} | {N N} | {O N O N} | {O} | {O N N O} | | {N O O N} |
Now we will count the possible arrangements. Of course we are over counting because the commutative operator (Plus and Times) may cut the permutation tree in half, but the problem is small enough not to be bother by that. (We are also overcounting in those cases where the sequence is {O O}. but we simply go on ..)
We have to choose 2 numbers in four for the first segment, that's 12 possible arrangements.
For the middle segment, the two remaining numbers may only be permuted, that is a factor 2
But we have another factor 5 for counting the five alternatives for the middle segment.
For the three operators, as they may repeat we have a factor 4^3=64
So the size of the problem is the product of the numbers in bold:12 2 5 64 = 7680. No optimization is needed, we may go ahead by brute force.
The rest of the problem is to build the 7680 arrangements and the RPN evaluator. Both relatively easy tasks.
I'll post it ...it's still a draft but here is too late! Will follow tomorrow!
Edit: RPN Evaluator
Here is the code for the recursive RPN evaluator. I choose to do it in a functional language (Mathematica) to simplify the operator parsing
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*)
];
];
Usage examples
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
a bit later I'll post the tuples generator, show that they are 7680 and some funny results about the distribution of the possible results of the operations (in fact for the {1,2,3,4} set you can only get 230 different results!).
Edit : Tuples construction
First we explicitly construct the possibilities for the middle segment
t1 = {{n3, n4, o1, o2},
{n3, o1, n4, o2},
{o1, n3, o2, n4},
{o1, n3, n4, o2},
{n3, o1, o2, n4}};
Now we prepend the two variations for {n1,n2} and the last operator
t2 = Join[Map[Join[{n1, n2}, #, {o3}] &, t1],
Map[Join[{n2, n1}, #, {o3}] &, t1]] ( bahh ... don't mind the code*)
Resulting in our 10 different configurations
Now we have to populate all those configurations with all the possible permutations of the numbers and operators.
We first construct all number permutations as assignment rules for our tuples
repListNumbers = (*construct all number permutations*)
Table[{n1 -> #[[1]], n2 -> #[[2]], n3 -> #[[3]], n4 -> #[[4]]} &[i],
{i, Permutations[{1, 2, 3, 4}]}];
These little beast have the form
{n1 -> 1, n2 -> 2, n3 -> 3, n4 -> 4}
And we can use them to replace vallues in our tuples. For example:
{n1,n2,n3,o1,o2,n4,o3} /. {n1 -> 1, n2 -> 2, n3 -> 3, n4 -> 4}
Results in
{1,2,3,o1,o2,4,o3}
Of course we may have constructed the replacement rules as a function to be able to change the number set at will. We do now something similar with the operators
repListOps = (*Construct all possible 3 element tuples*)
Table[{o1 -> #[[1]], o2 -> #[[2]], o3 -> #[[3]]} &[i],
{i, Tuples[{Plus, Times, Divide, Subtract}, 3]}];
So we get a collection of things like
{o1->Plus, o2->Plus, o3->Divide}
Now we combine our tuples and all our replacement rules in one big list:
t3 = Flatten[t2 /. repListNumbers /. repListOps, 2];
Which results in 15360 different calculations. But we know that there overcounted for a factor of two, so now we drop the repeated elements:
t3 =Union[t3]
And that give us our expected 7680 elements.
There are still some overcounting, because {2,3,Times} = {3,2,Times} = 6, but that is ok for our current purpouses.
Evaluating the results
Now we have our RPN evaluator and all those tuples, and we want to know if a certain final result is possible.
We simply have to ask if that number is contained in the set of results:
In[252]:= MemberQ[rpn /@ t3, 24]
Out[252]= True
In[253]:= MemberQ[rpn /@ t3, 38]
Out[253]= False
In fact the bounds for the result set are:
In[254]:= Max[rpn /@ t3]
Out[254]= Max[36, ComplexInfinity]
In[255]:= Min[rpn /@ t3]
Out[255]= Min[-23, ComplexInfinity]
The infinity results are due to the fact that I didn't care about divisions by zero, so they are there , just inside the set. The numeric interval is [-23,36].
If you want to know how many of the results are equal to 24, just count them
In[259]:= Length@Select[t3, rpn[#] == 24 &]
Out[259]= 484
Of course many of them are trivial permutations due to the commutative properties of "Plus" and "Times", but not all:
{1, 2, Plus, 3, Plus, 4, Times} -> ((1+2)+3)*4 = 24
{2, 1, 4, 3, Times, Divide, Divide} -> 2/(1/(4*3)) = 24
There are none sequence using "Subtract" that gives 24!
In[260]:= MemberQ[Flatten@Select[t3, rpn[#] == 24 &], Subtract]
Out[260]= False
Results Spectrum sample
这篇关于算法运算符和操作数的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
