获取数学表达式的每个排列

Question

任务

给定一个数字列表

例如：

1, 2, 3.

使用乘法或加法运算得到这些数字的每一个组合(*/+)

所以在上面的例子中，组合是

1+2+3

1+2*3

1*2*3

1*2+3

我写了一个基本的递归方法来解决它，我想到的方法如下

给定一个数字，我可以

添加下一个数字
乘以下一个数

这样你就得到了这样一棵树

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

等等...

但是输出输出每个答案两次

我使用 1,2,3 得到的输出是

1*2+3

1*2*3

1+2+3

1+2*3

我的问题

这是一个可接受的算法吗？如果是，我的代码出了什么问题
还有其他更有效的方法吗？

代码

    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() 函数两次，所以 ˋ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 2

我认为您的错误在于您将单个运算符传递给函数 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 3

显然我的回答有点晚了。问题是你没有遍历操作数。这是解决您问题的清晰代码。

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 4

有更好的解决方法。您的代码是递归的，因此运行时间会非常糟糕。会有一个更简单的解决方案：如果您有 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'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);
    }
}

注意：此代码还可以运行更多运算符或更多数字

Answer 5

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

你可以这样看这个问题。基本上你只需要生成你需要使用的运算符的排列。在这种情况下，他们会添加 + 和 * 因此，它们的排列是： + + + * * + * * 然后你只需要将它们插入到我在图中向你展示的运算符位置。编码部分留给你。

:)

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

获取数学表达式的每个排列

Get every permutation of a mathematical expression

java

algorithm

recursion

permutation

dynamic-programming

任务

这样你就得到了这样一棵树

我的问题

代码