Java

Question

假设我有一个像

这样的矩阵

|1,2,3|
|4,5,6|
|7,8,9|

我想要一个不同组合的总和列表，例如 12(1+4+7)、13(1+4+8) 等等，直到我拥有所有 27 种组合。除了使用数组和 for 循环之外，实现此目的的最佳方法是什么。我正在研究 Google Guava 的 Table 界面，但不确定这是否是最好的方法。

不同的组合 - 从上面的矩阵我生成不同的组合，如 (1,4,7),(1,4,8),(1,4,9),(1,5,7),( 1,5,8),(1,5,9),(1,6,7),(1,6,8),(1,6,9),(2,4,7),(2, 4,8) 等等，直到我得到所有 27 种组合，然后对每个组合中的值求和。

Answer 1

查看Apache Commons Math project, especially, the linear包。

Answer 2

你可以使用递归。我还没有测试下面的代码，但它应该可以解决问题。

//make this an instance field that the function sum() can access
ArrayList<Integer> matrixSums = new ArrayList<Integer>();

//call this line to put all the sums into matrixSums
getSums(matrix);

//helper function for the recursion (gets it started)
public void getSums(int[][] array)
{
    boolean[][] visited = new boolean[array.length][array[0].length];
    ArrayList<Integer> answer = new ArrayList<Integer>();

    for (int i = 0; i < array.length; i++)
    {
        for (int j = 0; j < array[i].length; j++)
        {
            visited[i][j] = true;
            sum(array, visited, 0, 0);
            visited[i][j] = false;
        }
    }

    return answer;
}

//does the actual recursion/math
public void sum(int[][] array, boolean[][] visited, int numVisited, int currentSum)
{
    //base case
    if (numVisited == 3)
    {
        matrixSums.add(currentSum);
        return;
    }

    //calculate sums
    for (int i = 0; i < array.length; i++)
    {
        for (int j = 0; j < array[i].length; j++)
        {
            if (!visited[i][j])
            {
                visited[i][j] = true;
                sum(array, visited, numVisited + 1, currentSum + array[i][j]);
                visited[i][j] = false;
            }
        }
    }
}

Answer 3

你可以像这样使用一个简单的递归函数：

 private static void findCombinations(int[][] matrix, int row, Integer[] currentArray) {
    if(row == matrix.length){
        LinkedList<Integer> list = new LinkedList<>(Arrays.asList(currentArray));
        result.add(list);
        return;
    }
    int cols = matrix[0].length;
    for(int i=0;i< cols;i++){
        currentArray[row]=matrix[row][i];
        findCombinations(matrix,row+1,currentArray);
    }
}

另一部分代码是：

static List<List<Integer>> result = new LinkedList<>();

我调用了如下函数：

int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};
findCombinations(matrix,0,new Integer[3]);

最后，您将拥有 result 列表中的所有 27 种组合，您可以轻松地对其进行迭代以获得总和。

Answer 4

如果你想要每个组合的总和，你可以使用如下所示的东西。如果我理解你的话，它已经过测试并且可以工作：

基于二维的矩阵 I table（将被打印）

位置class是为了得到数字在这个矩阵table中的坐标。

public class Position {

private int x;
private int y;

public Position(int x, int y){
    this.x=x;
    this.y=y;
}

public int getX()       {return x;}
public void setX(int x) {this.x = x;}
public int getY()       {return y;}
public void setY(int y) {this.y = y;}
public String toString(){
    return x+" x "+y;
}

}

矩阵具有二维 table 和矩阵并自行计算其和

public class Matrix {

//table int[x][y]
private int[][] table;

/** calculate sum for any table of number position */
public int sum(Position... positions){
    int sum=0;
    for(Position temp: positions){
        int number=table[temp.getX()][temp.getY()];
        sum+=number;
        System.out.println(temp.getX()+" x "+temp.getY()+": "+number);
    }
    System.out.println("sum:\t"+sum);
    System.out.println("-------------------");
    return sum;
}

/** calculate sum of every combination on matrix and return as list */
public List<Integer> calulaceAllCombinationSums(){
    List<Integer> sums=new ArrayList<Integer>();
    int rows=table[0].length; //number of arguments in sum method
    Position[] arguments=new Position[rows]; //table of positions to calculate sum 
    int[] indexInRow=new int[rows]; // index of table represents row number, and value represents which number of row get to calculate sum
    for(int i=0;i<rows;i++){ //fill table with default values
        indexInRow[i]=0;
    }

    boolean finished=false; //specify if find all combinations
    int combinationNumber=0; //count combinations
    while(!finished){
        combinationNumber++;
        for(int i=0;i<rows;i++){
            arguments[i]=new Position(indexInRow[i], i);//prepare posistion of number as argument
        }
        sums.add(sum(arguments));//calculate sum and add to list of results

        finished=check(indexInRow); //checks if we are found every combination
        recalculateIndexRow(indexInRow);//change combination to next
    }
    System.out.println("all combinations: "+combinationNumber);

    return sums;
}

/** check if all combination are used */
private boolean check(int[] rows){
    boolean result=true;
    for(int i=0;i<rows.length;i++){
        if(rows[i]<(table.length-1)){
            result=false;
        }
    }
    return result;
}

/** recalculation of inedexes bases on incrementation each row from first until the end of row. 
 * Start with first row, first position. Increments position until the end of row, then increased by 1 second row, and set first row on first position.
 * And works like that over and over again until last position of last row  */
private void recalculateIndexRow(int[] rows){
    for(int i=0;i<rows.length;i++){
        if(rows[i]<(table.length-1)){
            rows[i]=rows[i]+1;
            break;
        }else if(rows[i]==table.length-1){
            rows[i]=0;
        }
    }
}

//getters and setters below
public int[][] getTable() {return table;} //getter
public void setTable(int[][] table) {this.table = table;}//setter

}

测试 class 检查：

public class Test {

public static void main(String...strings ){
    int[][] table=prepareMatrix();

    Matrix matrix=new Matrix();
    matrix.setTable(table);

    List<Integer> results=matrix.calulaceAllCombinationSums();
}

private static int[][] prepareMatrix(){
    int i=0;
    int[][] table =new int[3][3];
    System.out.println("*************************");
    System.out.println("\t TABLE");
    System.out.println("X | Y | value");
    System.out.println("------------");
    for(int y=0;y<table[0].length;y++){
        for(int x=0;x<table.length;x++){
            table[x][y]=i++;
            System.out.println(x+" | "+y+" | "+(i-1));
            System.out.println("------------");
        }
    }
    System.out.println("*************************\n");
    return table;
}

}

Java - 矩阵中不同组合的总和列表

Java - List of sum of different combinations in a matrix

guava