所有可能的数值表达式 [英] all possible numerical expressions

问题描述

一个完全没用的问题：我买了一个数字游戏，它是由两个黑色骰子和5个彩色骰子组成的。两个黑色的数字组成一个2位数的数字，范围从11到66，其余5个是您可以使用的数字，将它们与所有可能的数值表达式结合起来使用以获取目标数字。

one totally useless question: I bought a numerical game, it's made of two black dice plus 5 coloured ones. the two black ones form a 2 digits number, ranging from 11 to 66, the other 5 are the numbers you can use, combining them in all possible numerical expressions with the task to obtain the target number.

例如，黑色40 + 2：目标42

for example, black 40 + 2: target 42

彩色5 3 6 2 4，您可以通过5 3 + 6获得目标* 4 2 +-（使用RPN，因为它可以避免使用方括号）。

coloured 5 3 6 2 4, you can obtain the target by 5 3 + 6 * 4 2 + - (using RPN because it avoids brackets).

现在我想在人们玩游戏时使用便携式计算机找到最佳答案。

now I'd like to use my pocket computer to find the best answer while we people play the game.

我必须说我对解决方案并没有太认真的考虑，我只是在寻找寻找参数置换的部分，然后是如何生成从那可能的表达？我会使用RPN并枚举表达式的所有可能的形状，然后用+-* /填充空格。

I must say I didn't really think too hard about the solution yet, I just looked for the part on finding the permutations of the arguments, but then how to generate the possible expressions from that? I would do that using RPN and enumerating all possible "shapes" of expressions and then fill in the blanks with +-*/.

我不认识

输出将是这样的：
..... xxxx
.... x.xxx
... x..xxx
..x ... xxx
.... xx.xx
... xxxx
..x .. x.xx
... xx..xx
..xx.xx
.... xxx.x
... x.xx.x
..x..xx.x
... xx.xx
..xxxx

the output would be this: .....xxxx ....x.xxx ...x..xxx ..x...xxx ....xx.xx ...x.x.xx ..x..x.xx ...xx..xx ..x.x..xx ....xxx.x ...x.xx.x ..x..xx.x ...xx.x.x ..x.x.x.x

诸如：
..xx ... xx
... xxx..x
..x.xx..x
..x.xx..x
无效，因为第二个或第三个运算符会找到一个操作数。

things like: ..xx...xx ...xxx..x ..x.xx..x ..x.xx..x are invalid, as the second or third operator would find one operand.

我可以使用硬编码列表，但是看起来确实很丑！

I can use a hard coded list, but it looks really ugly!

推荐答案

我认为您正在寻找的是大小为5的完整二叉树的枚举。（此类对象的数量是第五个加泰罗尼亚编号，为14。）。枚举是直接的，基于加泰罗尼亚语数字的标准递归：



对于每个（i，5-i），用生成所有树i 叶子，以及所有 5-i 叶子的树，对于每个集合中一棵树的每种组合，通过一个根节点，其左子节点来自第一个集合，而其右子节点来自第二个集合。如果您不想使用树，请直接使用RPN：

What I think you're looking for is the enumeration of full binary trees of size 5. (The count of such objects is the fifth Catalan number, which is 14.). The enumeration is straight-forward, based on the standard recursion for Catalan numbers:

For each (i, 5-i), produce all the trees with i leaves, and all the trees with 5-i leaves, and for each combination of one tree from each set, construct a new tree by making a root node whose left child comes from the first set and whose right child comes from the second set. If you don't want to use trees, use RPN directly:

# Produces all possible RPN layouts with n values and n-1 binary operators,
# representing values as '#' and operators as '+'
def RPN(n):
  if n == 1:
    yield '#'
  for i in range(1,n):
    for left in RPN(i):
      for right in RPN(n - i):
        yield left + right + '+' 

当然，还有一元运算符。如果允许的话，它将变得更加复杂。

Of course, there are unary operators as well. If you allow those, it gets more complicated.

请注意，您可以直接修改上面的内容以直接插入参数。而不是将n分为（i，n-i），您会​​发现n个值的集合的所有分区都是两个非空子集。 （否则，您只需找到一组数字的所有排列，然后将它们插入生成的RPN表达式即可。）

Note that you can directly adapt the above to insert the arguments directly; instead of dividing n into (i, n-i), you would find all the partitions of the set of n values into two non-empty subsets. (Otherwise, you can just find all the permutations of the set of numbers, and plug them into the resulting RPN expressions.)

然后，您需要做的全部是插入所有可能的运算符序列（如果只允许+，-，*和/，则有4 ⁴ = 256种可能性）。

Then "all" you need to do is insert all possible operator sequences (if you only allow +,-,* and / then you have 4⁴ = 256 possibilities).

因此如果五个数字不同，则最终将为14 * 5！ * 4 ⁴ = 430080要测试的表达式。

So if the five numbers were distinct, you would end up with 14 * 5! * 4⁴ = 430080 expressions to test.

这篇关于所有可能的数值表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！