所有可能的数值表达式

Question

一个完全没用的问题：我买了一个数字游戏，它由两个黑色骰子加上5个彩色骰子组成。两个黑色的组成一个2位数的数字，范围从11到66，另外5个是你可以使用的数字，将它们组合在所有可能的数字表达式中，以获得目标数字。在

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

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

现在我想用我的掌上电脑在我们玩游戏的时候找到最好的答案。在

我必须说，我并没有认真考虑解决方案，我只是寻找了寻找论点排列的部分，但是如何从中产生可能的表达式呢？我会用RPN和枚举所有可能的表达式“形状”，然后用+-*/填充空格。在

我不知道列举表达式的形状有什么问题。在

输出结果如下： ……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 无效，因为第二个或第三个运算符将找到一个操作数。在

我可以使用硬编码列表，但它看起来真的很难看！在

Answer 1

我想你要找的是5大小的完整二叉树的枚举。（此类对象的计数是第五个Catalan number，即14）。枚举是直接向前的，基于Catalan数字的标准递归：

对于每个（i，5-i），生成具有i叶的所有树和具有{}叶的所有树，对于每个集合中一棵树的每个组合，通过创建一个根节点来构造一个新树，根节点的左子节点来自第一个集，右子节点来自第二个集合。如果不想使用树，请直接使用RPN：

# 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 + '+' 

当然，也有一元运算符。如果你允许的话，事情会变得更复杂。在

请注意，您可以直接调整上面的方法来直接插入参数；而不是将n划分为（i，n-i），而是将n个值集的所有分区划分为两个非空子集。（否则，您只需找到这组数字的所有排列，并将它们插入结果RPN表达式中。）

然后“所有”你需要做的就是插入所有可能的运算符序列（如果你只允许+，-，*和/然后你有4个⁴=256个可能性）。在

所以如果这五个数字是不同的，你会得到14*5！*4⁴=430080个要测试的表达式。在

Answer 2

枚举不同数字块数的问题是可以应用于集合http://en.wikipedia.org/wiki/Partition_of_a_set的分区数