Tamir Shklaz Tamir Shklaz - 6 months ago 17
Java Question

Get every permutation of a mathematical expression

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

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)

Comments