Using + - * / operators and 4 4 4 4 digits find all formulas that would resolve to 1 2 3 4 5 6 7 8 9 10 I had a conversation with a colleague of mine and he brought up an interesting problem. Using the + - * / operators and four 4 4 4 4 digits, create an algorithm that will output all the formulas that would equate to 1 or 2 or 3 or 4 or 5 or 6 or 7 or 9 or 10
Example of results
1 = (4/4/4)*4  
2 = (4*4)/(4+4)  
3 = (4+4+4)/4  
4 = 4+(4*(4-4))  
5 = ((4*4)+4)/4  
6 = 4+((4+4)/4)  
7 = (4+4)-(4/4)  
8 = (4/4)*(4+4)  
9 = (4+4)+(4/4)  
10 = (44-4)/4  

But is should output all possible combinations of the above example.
The question is not what the resulting formulas are but how should I approach creating the algorithm that produces the desired result under specific conditions like the ones above.
 A: Create a recursion that uses the reverse Polish notation. Here is a pseudo-code:
function rec(digitsLeft, numbers, operators, expression):
    if digitsLeft == 0 and numbers - operators == 1:
        value = evaluate(expression)
        if value in {1..10}: output expression
        return
    if digitsLeft > 0:
        rec(digitsLeft - 1, numbers + 1, operators, [expression, 4])
    if digitsLeft > 1:
        rec(digitsLeft - 2, numbers + 1, operators, [expression, 44])
    if numbers - operators > 1:
        for op in ['+', '-', '*', '/']:
            rec(digitsLeft, numbers, operators + 1, [expression, op])

The reverse Polish notation will take care of operators' precedence, so you don't have to handle brackets.
The initial call is:
rec(4, 0, 0, [])

and the parameters are:


*

*digitsLeft -- how many digits do we still need to use,

*numbers -- how many numbers our expression already has,

*operators -- how many operators our expression already has,

*expression -- the array holding the elements of the expression.


Of course, you need to write evaluate (the function that evaluates expression) and output (the function that will most likely convert the reverse Polish notation expression to the standard infix notation (using some of the known algorithms, for example this one) and print it to the screen or a file).
A more general version would replace this:
    if digitsLeft > 0:
        rec(digitsLeft - 1, numbers + 1, operators, [expression, 4])
    if digitsLeft > 1:
        rec(digitsLeft - 2, numbers + 1, operators, [expression, 44])

with a loop that would go through $4$, $44$, etc., but for this example, it was easier to do just a copy/paste of two if-s.
If you need any further clarification, please ask.
A: I suggest you use recursion.  If $S(k)$ are all the formulas using $k$ 4's, 
a formula using $k+1$ 4's is either
$A + B$, $A * B$, $A - B$, $A / B$ where $A$ and $B$ use $j$ and $k+1-j$ 4's respectively,
$j = 1 \ldots k$, or it is the concatenation of $k+1$ 4's.  
Construct each 
formula, evaluate carefully (watch out for division by $0$), and select those
where the result is one of the desired ones.
A: As an extension, rather than an answer ... If radicals and/or factorials are added to the set of operators, then the number of ways one can combine the digits of an integer changes from being a finite combinatorical problem to an infinite one. This is because one can repeatedly nest the √ and ! operators to any arbitrary depth (for example, 4!!!!!!!). 
A few years ago, I wrote some code in Mathematica to do this, to arbitrary level of nesting. For the problem at hand (4444), and allowing radicals, here is some sample output (only the first 9 variations for each number are shown here):

To view a magnified version:  http://www.tri.org.au/se/4444.png
A related topic is:
"Pretty Wild Narcissistic Numbers - Numbers that pwn",  http://www.tri.org.au/numQ/pwn/
and a paper I wrote on the radical case:
Rose, C (2005), "Radical Narcissistic Numbers", Journal of Recreational Mathematics, 33(4), 2004-2005, 250-254
which also contains references to related literature.
