Computing target number from numbers in a set

I'm working on a homework problem that asks me this:

Tiven a finite set of numbers, and a target number, find if the set can be used to calculate the target number using basic math operations (add, sub, mult, div) and using each number in the set exactly once (so I need to exhaust the set). This has to开发者_开发技巧 be done with recursion.

So, for example, if I have the set

{1, 2, 3, 4}

and target 10, then I could get to it by using

((3 * 4) - 2)/1 = 10. 

I'm trying to phrase the algorithm in pseudo-code, but so far haven't gotten too far. I'm thinking graphs are the way to go, but would definitely appreciate help on this. thanks.

This isn't meant to be the fastest solution, but rather an instructive one.

• It recursively generates all equations in postfix notation
• It also provides a translation from postfix to infix notation
• There is no actual arithmetic calculation done, so you have to implement that on your own
  • Be careful about division by zero

With 4 operands, 4 possible operators, it generates all 7680 = 5 * 4! * 4^3 possible expressions.

• 5 is Catalan(3). Catalan(N) is the number of ways to paranthesize N+1 operands.
• 4! because the 4 operands are permutable
• 4^3 because the 3 operators each have 4 choice

This definitely does not scale well, as the number of expressions for N operands is [1, 8, 192, 7680, 430080, 30965760, 2724986880, ...].

In general, if you have n+1 operands, and must insert n operators chosen from k possibilities, then there are (2n)!/n! k^n possible equations.

Good luck!

import java.util.*;

public class Expressions {
    static String operators = "+-/*";

    static String translate(String postfix) {
        Stack<String> expr = new Stack<String>();
        Scanner sc = new Scanner(postfix);
        while (sc.hasNext()) {
            String t = sc.next();
            if (operators.indexOf(t) == -1) {
                expr.push(t);
            } else {
                expr.push("(" + expr.pop() + t + expr.pop() + ")");
            }
        }
        return expr.pop();
    }

    static void brute(Integer[] numbers, int stackHeight, String eq) {
        if (stackHeight >= 2) {
            for (char op : operators.toCharArray()) {
                brute(numbers, stackHeight - 1, eq + " " + op);
            }
        }
        boolean allUsedUp = true;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] != null) {
                allUsedUp = false;
                Integer n = numbers[i];
                numbers[i] = null;
                brute(numbers, stackHeight + 1, eq + " " + n);
                numbers[i] = n;
            }
        }
        if (allUsedUp && stackHeight == 1) {
            System.out.println(eq + " === " + translate(eq));
        }
    }
    static void expression(Integer... numbers) {
        brute(numbers, 0, "");
    }

    public static void main(String args[]) {
        expression(1, 2, 3, 4);
    }
}

Before thinking about how to solve the problem (like with graphs), it really helps to just look at the problem. If you find yourself stuck and can't seem to come up with any pseudo-code, then most likely there is something that is holding you back; Some other question or concern that hasn't been addressed yet. An example 'sticky' question in this case might be, "What exactly is recursive about this problem?"

Before you read the next paragraph, try to answer this question first. If you knew what was recursive about the problem, then writing a recursive method to solve it might not be very difficult.

You want to know if some expression that uses a set of numbers (each number used only once) gives you a target value. There are four binary operations, each with an inverse. So, in other words, you want to know if the first number operated with some expression of the other numbers gives you the target. Well, in other words, you want to know if some expression of the 'other' numbers is [...]. If not, then using the first operation with the first number doesn't really give you what you need, so try the other ops. If they don't work, then maybe it just wasn't meant to be.

Edit: I thought of this for an infix expression of four operators without parenthesis, since a comment on the original question said that parenthesis were added for the sake of an example (for clarity?) and the use of parenthesis was not explicitly stated.

Well, you didn't mention efficiency so I'm going to post a really brute force solution and let you optimize it if you want to. Since you can have parantheses, it's easy to brute force it using Reverse Polish Notation:

First of all, if your set has n numbers, you must use exactly n - 1 operators. So your solution will be given by a sequence of 2n - 1 symbols from {{your given set}, {*, /, +, -}}

st = a stack of length 2n - 1
n = numbers in your set
a = your set, to which you add *, /, +, -
v[i] = 1 if the NUMBER i has been used before, 0 otherwise

void go(int k)
{
  if ( k > 2n - 1 ) 
  {
    // eval st as described on Wikipedia. 
    // Careful though, it might not be valid, so you'll have to check that it is   
    // if it evals to your target value great, you can build your target from the given numbers. Otherwise, go on.

    return;
  }

  for ( each symbol x in a )
    if ( x isn't a number or x is a number but v[x] isn't 1 )
    {
      st[k] = x;
      if ( x is a number )
        v[x] = 1;

      go(k + 1);
    }
}

Generally speaking, when you need to do something recursively it helps to start from the "bottom" and think your way up. Consider: You have a set S of n numbers {a,b,c,...}, and a set of four operations {+,-,*,/}. Let's call your recursive function that operates on the set F(S)

• If n is 1, then F(S) will just be that number.
• If n is 2, F(S) can be eight things:
  • pick your left-hand number from S (2 choices)
  • then pick an operation to apply (4 choices)
  • your right-hand number will be whatever is left in the set
• Now, you can generalize from the n=2 case:
  • Pick a number x from S to be the left-hand operand (n choices)
  • Pick an operation to apply
  • your right hand number will be F(S-x)

I'll let you take it from here. :)

edit: Mark poses a valid criticism; the above method won't get absolutely everything. To fix that problem, you need to think about it in a slightly different way:

• At each step, you first pick an operation (4 choices), and then
• partition S into two sets, for the left and right hand operands,
• and recursively apply F to both partitions

Finding all partitions of a set into 2 parts isn't trivial itself, though.

Your best clue about how to approach this problem is the fact that your teacher/professor wants you to use recursion. That is, this isn't a math problem - it is a search problem.

Not to give too much away (it is homework after all), but you have to spawn a call to the recursive function using an operator, a number and a list containing the remaining numbers. The recursive function will extract a number from the list and, using the operation passed in, combine it with the number passed in (which is your running total). Take the running total and call yourself again with the remaining items on the list (you'll have to iterate the list within the call but the sequence of calls is depth-first). Do this once for each of the four operators unless Success has been achieved by a previous leg of the search.

I updated this to use a list instead of a stack

When the result of the operation is your target number and your list is empty, then you have successfully found the set of operations (those that traced the path to the successful leaf) - set the Success flag and unwind. Note that the operators aren't on a list nor are they in the call: the function itself always iterates over all four. Your mechanism for "unwinding" the operator sequence from the successful leaf to get the sequence is to return the current operator and number prepended to the value returned by recursive call (only one of which will be successful since you stop at success - that, obviously, is the one to use). If none are successful, then what you return isn't important anyhow.

Update This is much harder when you have to consider expressions like the one that Daniel posted. You have combinatorics on the numbers and the groupings (numbers due to the fact that / and - are order sensitive even without grouping and grouping because it changes precedence). Then, of course, you also have the combinatorics of the operations. It is harder to manage the differences between (4 + 3) * 2 and 4 + (3 * 2) because grouping doesn't recurse like operators or numbers (which you can just iterate over in a breadth-first manner while making your (depth-first) recursive calls).

Here's some Python code to get you started: it just prints all the possible expressions, without worrying too much about redundancy. You'd need to modify it to evaluate expressions and compare to the target number, rather than simply printing them.

The basic idea is: given a set S of numbers, partition S into two subsets left and right in all possible ways (where we don't care about the order or the elements in left and right), such that left and right are both nonempty. Now for each of these partitions, find all ways of combining the elements in left (recursively!), and similarly for right, and combine the two resulting values with all possible operators. The recursion bottoms out when a set has just one element, in which case there's only one value possible.

Even if you don't know Python, the expressions function should be reasonably easy to follow; the splittings function contains some Python oddities, but all it does is to find all the partitions of the list l into left and right pieces.

def splittings(l):
    n = len(l)
    for i in xrange(2**n):
        left = [e for b, e in enumerate(l) if i & 2**b]
        right = [e for b, e in enumerate(l) if not i & 2**b]
        yield left, right

def expressions(l):
    if len(l) == 1:
        yield l[0]
    else:    
        for left, right in splittings(l):
            if not left or not right:
                continue
            for el in expressions(left):
                for er in expressions(right):
                    for operator in '+-*/':
                        yield '(' + el + operator + er + ')'

for x in expressions('1234'):
    print x

pusedo code:

Works(list, target)
for n in list
tmp=list.remove(n)
return Works(tmp,target+n) or Works(tmp,target-n) or Works(tmp, n-target) or ...

then you just have to put the base case in. I think I gave away to much.