Algorithm to get all the possible combinations of operations from a given numbers

Question

I want to write a function that given a set of numbers, for example: 2, 3

It returns all the combinations of operations with +, -, *, and /.

The result for these two numbers would be:

2+3   
2-3  
2*3  
2/3 

For the numbers: 2, 3, 4 it would be:

(2+3)+4   
(2+3)-4  
(2+3)*4  
(2+3)/4

(2-3)+4  
(2-3)-4  
(2-3)*4  
(2-3)/4  

...

2+(3+4)
2+(3*4)
2+(3-4)
2+(3/4)

...

3+(2+4)
3+(2*4)
3+(2-4)
3+(2/4)

...
and so on

The order of the operators doesn't matter, the point is to obtain all the results from all the possible combinations of operations.

Answer 1

I would tackle this by using Reverse Polish Notation, where you can just append operators and operands to a string while being considerate to a few simple rules.

For example, the expression 2 + (3 * 4) would be 2 3 4 * + in Reverse Polish Notation. On the other hand, (2 + 3) * 4 would be 2 3 + 4 *.

If we already have a partial expression, we can either add an operand or an operator.

Adding an operand can always be done and will increase the size of the stack by 1. On the other hand, adding an operator decreases the size of the stack by 1 (remove the two top-most operands and add the result) and can therefore only be done if the stack has at least two entries. At the end, to form a valid expression, the stack size has to be exactly 1.

This motivates a recursive function with the following interface:

getSubexpressions(remainingOperands, currentStackSize)

The function returns a list of subexpressions that can be appended to a partial expression with stack size currentStackSize and using the operands remainingOperands.

The base case of this recursive function is when there are no more remaining operands and the stack size is 1:

if remainingOperands = ∅ and currentStackSize = 1
    return { "" }

In this case, we can only add the empty string to the expression.

In all other cases, we need to gather a set of subexpressions

subexpressions = { }   // initialize an empty set

If we can add an operator, we can simply append it:

if currentStackSize >= 2
    for each possible operator o
        subexpressions.add(o + getSubexpressions(remainingOperands, currentStackSize - 1))

The notation o + getSubexpressions(remainingOperands, currentStackSize - 1) is shorthand for concatenating the operand o with all subexpressions returned from the call to getSubexpressions().

We are almost there. The last remaining bit is to add potential operands:

for each o in remainingOperands
    subexpressions.add(o + getSubexpressions(remainingOperands \ { o }, currentStackSize + 1))

The notation remainingOperands \ { o } stands for set difference, i.e., the set of remaining operands without o.

That's it. In full:

getSubexpressions(remainingOperands, currentStackSize)
    if remainingOperands = ∅ and currentStackSize = 1
        return { "" }

    subexpressions = { }   // initialize an empty set

    if currentStackSize >= 2
        for each possible operator o
            subexpressions.add(o + getSubexpressions(remainingOperands, currentStackSize - 1))

    for each o in remainingOperands
        subexpressions.add(o + getSubexpressions(remainingOperands \ { o }, currentStackSize + 1))

    return subexpressions

This recursive call will usually have overlapping subcalls. Therefore, you can use memoization to cache intermediate results instead of re-calculating them over and over.

Here is a proof-of-concept implementation without memoization in C#. Expecially the operand management can be designed more efficiently with more appropriate data structures:

static void Main(string[] args)
{
    foreach (var expr in GetSubexpressions(new List<string> { "1", "2", "3" }, 0, new StringBuilder()))
    {
        Console.WriteLine(expr);
    }
}

static char[] operators = { '+', '-', '*', '/' };

static IEnumerable<StringBuilder> GetSubexpressions(IList<string> remainingOperands, int currentStackSize, StringBuilder sb)
{
    if (remainingOperands.Count() == 0 && currentStackSize == 1)
    {
        yield return sb;
        yield break;
    }

    if(currentStackSize >= 2)
    {
        foreach (var o in operators)
        {
            sb.Append(o);
            foreach (var expr in GetSubexpressions(remainingOperands, currentStackSize - 1, sb))
                yield return expr;
            sb.Remove(sb.Length - 1, 1);
        }
    }

    for (int i = 0; i < remainingOperands.Count; ++i)
    {
        var operand = remainingOperands[i];
        remainingOperands.RemoveAt(i);
        sb.Append(operand);
        foreach (var expr in GetSubexpressions(remainingOperands, currentStackSize + 1, sb))
            yield return expr;
        sb.Remove(sb.Length - operand.Length, operand.Length);
        remainingOperands.Insert(i, operand);
    }
} 

The program prints the following output:

12+3+
12-3+
12*3+
12/3+
12+3-
12-3-
12*3-
12/3-
12+3*
12-3*
12*3*
12/3*
12+3/
12-3/
12*3/
12/3/
123++
123-+
123*+
123/+
123+-
123--
123*-
123/-
123+*
123-*
123**
123/*
123+/
123-/
123*/
123//
13+2+
13-2+
13*2+
13/2+
13+2-
13-2-
13*2-
13/2-
13+2*
13-2*
13*2*
13/2*
13+2/
13-2/
13*2/
13/2/
132++
132-+
132*+
132/+
132+-
132--
132*-
132/-
132+*
132-*
132**
132/*
132+/
132-/
132*/
132//
21+3+
21-3+
21*3+
21/3+
21+3-
21-3-
21*3-
21/3-
21+3*
21-3*
21*3*
21/3*
21+3/
21-3/
21*3/
21/3/
213++
213-+
213*+
213/+
213+-
213--
213*-
213/-
213+*
213-*
213**
213/*
213+/
213-/
213*/
213//
23+1+
23-1+
23*1+
23/1+
23+1-
23-1-
23*1-
23/1-
23+1*
23-1*
23*1*
23/1*
23+1/
23-1/
23*1/
23/1/
231++
231-+
231*+
231/+
231+-
231--
231*-
231/-
231+*
231-*
231**
231/*
231+/
231-/
231*/
231//
31+2+
31-2+
31*2+
31/2+
31+2-
31-2-
31*2-
31/2-
31+2*
31-2*
31*2*
31/2*
31+2/
31-2/
31*2/
31/2/
312++
312-+
312*+
312/+
312+-
312--
312*-
312/-
312+*
312-*
312**
312/*
312+/
312-/
312*/
312//
32+1+
32-1+
32*1+
32/1+
32+1-
32-1-
32*1-
32/1-
32+1*
32-1*
32*1*
32/1*
32+1/
32-1/
32*1/
32/1/
321++
321-+
321*+
321/+
321+-
321--
321*-
321/-
321+*
321-*
321**
321/*
321+/
321-/
321*/
321//