Get every permutation of a mathematical expression

Question

Task

Given a list of numbers

Eg:

1, 2, 3.

Get every combination of these numbers using the operations of multiplication or addition (*/+)

So in the above example the combinations would be

1+2+3

1+2*3

1*2*3

1*2+3

Ive written a basic recursive method to solve it, the way I thought about it was as follows

Given a number I can either

1. Add the next number

2. Multiply the next number

Thus you get a tree like this

           START NUMBER
              /   \
             *     +
            / \   /  \
           *   + *    +

Etc...

But the output outputs every answer twice

The output I get when using 1,2,3 is

1*2+3

1*2+3

1*2*3

1*2*3

1+2+3

1+2+3

1+2*3

1+2*3

My Question

1. Is this an acceptable algorithm and if so what is going wrong with my code

2. Is there another more efficient way of doing this.

CODE

    package AG;

import java.util.LinkedList;
import java.util.Stack;

/**
 *
 * @author Tamir Shklaz
 */
public class ArithmeticGame {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();
        LinkedList<Integer> number = new LinkedList<>();
        for (int i = 1; i <= 3; i++) {
            numbers.add(i);
        }
        permutateSigns('*', numbers, 0, "");
        permutateSigns('+', numbers, 0, "");

    }


    public static void permutateSigns(char operation, LinkedList<Integer> number, int pos, String expresion) {
        double sum = 0;
        if (pos == number.size()-1) {
            expresion += number.get(pos);
            System.out.println(expresion);


        } else {
            expresion += (Integer.toString(number.get(pos)) + Character.toString(operation));
            permutateSigns('+', number, pos + 1, expresion);
            permutateSigns('*', number, pos + 1, expresion);
        }

    }
}

Answer 1

Your mistake is that when increasing the postion the last time you are calling the permutateSigns() function twice, so the ˋpos == number.get(pos)ˋ is true twice for every combination. One time the following sign would have been + and second time *. A very quick fix would be to only Output a solution if the operation char is '+' for example

if(operation=='+')
  System.out.println(expression);

For a more elegant solution you would probably have to rearrange the operations / change the algorithm flow.

---

Here I changed the algorithm to first put an operator and then a number

 public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();
        LinkedList<Integer> number = new LinkedList<>();
        for (int i = 1; i <= 3; i++) {
            numbers.add(i);
         }
        permutateSigns('*', numbers, 1, numbers.get(0).toString());
        permutateSigns('+', numbers, 1, numbers.get(0).toString());
    }

    public static void permutateSigns(char operation, LinkedList<Integer> number, int pos, String expression) {
        if (pos == number.size()-1) {
            expression = expression + operation + number.get(pos);
            System.out.println(expression);
        } else {
            expression += ( Character.toString(operation) + Integer.toString(number.get(pos)));
            permutateSigns('+', number, pos + 1, expression);
            permutateSigns('*', number, pos + 1, expression);
        }

    }
}

Answer 2

I think your mistake is that you pass a single operator to the function permutateSigns instead of giving all operators.

Therefore you call the same function twice at the beginning, which results in doubled answers.

Here is the corrected code (I think it is what you need)

public class ArithmeticGame {

    public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();
        for (int i = 1; i <= 3; i++) {
            numbers.add(i);
        }
        char[] operations = { '*', '+' };
        permutateSigns(operations, numbers, 0, "");
    }

    public static void permutateSigns(char[] operations, LinkedList<Integer> numbers, int pos, String expression) {
        expression += numbers.get(pos);
        if (pos == numbers.size() - 1) {
            System.out.println(expression);
        } else {
            for (char operation : operations) {
                permutateSigns(operations, numbers, pos + 1, expression + operation);
            }
        }
    }
}

Additionally, I would advise you to use ArrayList instead of LinkedList, because get operations which are performed will have O(1) time instead of O(n)

Answer 3

There is a way better solution. You're code is recursive, and will have a horrible runtime due to this. There would be a far simpler solution: if you have n operators and m numbers to add, you have a total of n ^ (m - 1) possible combinations. by encoding each operator as a number, you can create a n-based number. or the other way round: each number in (0 , n ^ (m - 1) can be parsed into a combination of operators.

public static void main(String[] args){
    int[] numbers = {1 , 2 , 3};
    String[] operators = {"+" , "*"};

    int maxEnc = 1;
    for(int i = 0 ; i < numbers.length - 1 ; i++)
        maxEnc *= operators.length;

    int[] digits = new int[operators.length];
    int tmp;
    for(int i = 0 ; i < maxEnc ; i++){
        tmp = i;

        //interprete tmp as a n-based number and retrieve it's digits
        for(int j = 0 ; j < operators.length ; j++){
            digits[j] = tmp % operators.length;
            tmp /= operators.length;
        }

        String result = "";
        for(int j = 0 ; j < numbers.length - 1 ; j++)
            //reinterpret the digits as operators
            result += numbers[j] + operators[digits[j]];
        result += numbers[numbers.length - 1];

        System.out.println(result);
    }
}

NOTE: this code would aswell run with more operators or more numbers

Answer 4

Apparently im bit late with my answer. The problem was that u weren't iterating throu operands. Here's the clear code that solves your problem.

public class Test {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= 3; i++) {
            numbers.add(i);
        }
        permutateSigns(' ', numbers, 0, "");
    }

    public static void permutateSigns(char operation, List<Integer> number, int pos, String expresion) {
        expresion += number.get(pos);
        if (pos == number.size() - 1) {
            System.out.println(expresion);
        } else {
            for (Operands operand : Operands.values()) {
                permutateSigns(operand.getValue(), number, pos + 1, expresion + operand.getValue());
            }
        }
    }

    public enum Operands {

        ADD('+'), MULTIPLY('*');
        private final char operand;

        private Operands(char operand) {
            this.operand = operand;
        }

        public char getValue() {
            return operand;
        }
    }
}

Answer 5

+----+-------+------+-------+------+
|    |       |      |       |      |
| 1  |   op1 | 2    |  op2  |  3   |
+----------------------------------+
|    |       |      |       |      |
|    |       |      |       |      |
+----------------------------------+
|    |       |      |       |      |
|    |       |      |       |      |
|    |       |      |       |      |
|    |       |      |       |      |
|    |       |      |       |      |
|    |       |      |       |      |
+----+-------+------+-------+------+

You can see this problem as this. Basically you just need to generate pemutations of operators you need to use. In this case they ad + and * So, permuation of them are: + + + * * + * * Then you just need to insert them into to operator places I showed you in the diagram. Leave you for coding part.

:)

Answer 6

Javascript given to sets, the first for operands, shall be applied on the second set of number, then we evaluate generated expression with a target value.

var targetValue=10;
var set=[2,4,8,16,64];
//var ops=['+','-', '/', '*'];

var retArray=new Array();

function permutateSigns(operand, numbers, pos, epx){

        var sum = 0;
        if (pos == numbers.length-1) {
            epx += numbers[pos];
            //console.log(epx);
            retArray.push(epx);
        } else {
            epx += (numbers[pos]) + operand;
            permutateSigns('+', numbers, pos + 1, epx);
            permutateSigns('-', numbers, pos + 1, epx);
            permutateSigns('*', numbers, pos + 1, epx);
            permutateSigns('/', numbers, pos + 1, epx);
        }
    }
permutateSigns('+',set,0,"");
var per=retArray;
console.log(per);

var validExpr;
for (var i = 0; i < retArray.length; i++) {
    var result=eval(retArray[i]);

    if(result===targetValue)
        validExpr= retArray[i];
    else
     console.log(retArray[i] + ":" + eval(retArray[i]));
}
console.log("valid expression is:" + validExpr + "; value:"+ eval(validExpr) + "number of permutations is:"+ retArray.length);