Get every permutation of a math expression

Question

Task

Given a list of numbers

For instance:

1, 2, 3.

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

So in the above example the combination would be

1 + 2 + 3

1 + 2 * 3

1 * 2 * 3

1 * 2 + 3

Ive written a basic recursive method to solve it, since I thought about it as follows

Given the number, I can either

• Add the following number

• Multiply the next number

So you get a tree like this

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

Etc ...

But the output displays each answer twice

The output that 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

• Is this an acceptable algorithm, and if so, what happens to my code

• Is there an even more efficient way to do 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

, , permutateSigns .

, .

( , , )

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);
            }
        }
    }
}

, ArrayList LinkedList, get O ( 1) O (n)

Answer 2

, permutateSigns() , 'pos == number.get(pos) ' . + *. , char "+",

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

, , / .

---

, ,

 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 3

. - , - . : n m, , n ^ (m - 1) . , n. : (0 , n ^ (m - 1) .

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 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);
    }
}

:

Answer 4

-, . , u . , .

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   |
+----------------------------------+
|    |       |      |       |      |
|    |       |      |       |      |
+----------------------------------+
|    |       |      |       |      |
|    |       |      |       |      |
|    |       |      |       |      |
|    |       |      |       |      |
|    |       |      |       |      |
|    |       |      |       |      |
+----+-------+------+-------+------+

. , . ad + * , : + + + * * + * * , . .

:)

Answer 6

Javascript , , .

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);