all possible numerical expressions

Question

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.

for example, black 40 + 2: target 42

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.

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 +-*/.

I don't recognize the problem of enumerating the shapes of the expressions.

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

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!

Answer 1

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.

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.)

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

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

Answer 2

The problem of enumerating the number of different digit blocks is the number of partitions you can apply to a set http://en.wikipedia.org/wiki/Partition_of_a_set