java - 如何找到从唯一数组索引提取的数组中数字的最大可能总和

Question

我需要找到数组中数字的最大可能总和，但数字必须从唯一的数组索引中提取......就像这样:

double maxSum = 0;

double a = {1.0 , 2.0, 3.0};
double b = {4.0 , 5.0, 6.0};
double c = {7.0 , 8.0, 9.0};

sum = a[0] + b[1] + c[2];

// or sum = a[0] + b[2] + c[1]
// or sum = a[1] + b[0] + c[2]
// etc. - how to do that for i arrays and for j numbers in array?

if(sum >=maxSum){
maxSum = sum;
} 

这就是我所做的 - 但不知道下一步该做什么...

    public ArrayList<Double[]> tempArrayCreator() {
    ArrayList<Double[]> lists = new ArrayList<Double[]>();

    Double[] list1 = { 6.0, 7.0, 6.0 };
    Double[] list2 = { 4.5, 6.0, 6.75 };
    Double[] list3 = { 6.0, 5.0, 9.0 };

    lists.add(list1);
    lists.add(list2);
    lists.add(list3);

    return lists;
}

public double maxPossibleSum(ArrayList<Double[]> lists) {

    double result = 0.0;

    for (int i = 0; i < lists.size(); i++) {
        for (int j = 0; j < lists.get(i).length; j++) {

        // ???

        }
    }

    return result;

}

编辑。示例:

list1 = { 1, 5, 2};
list2 = { 9, 3, 7};
list3 = { 8, 4, 9};

possible solutions:
list1[0] + list2[1] + list3[2] = 13
list1[0] + list2[2] + list3[1] = 12
list1[1] + list2[0] + list3[2] = 23 <-- here it is!
list1[1] + list2[2] + list3[0] = 20
list1[2] + list2[0] + list3[1] = 15
list1[2] + list2[1] + list3[0] = 13

Answer 1

首先，您想要获取索引的所有排列的列表。

{[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 1, 0], [2, 0, 1]}

例如，这个answer给出了一种方法:

public static List<List<Integer>> getAllPermutations(int arraySize) {
    List<Integer> elements = new ArrayList<Integer>();
    for (int i = 0; i < arraySize; i++) {
        elements.add(i);
    }
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    getAllPermutations(result, elements, 0);
    return result;
}

private static void getAllPermutations(List<List<Integer>> result, List<Integer> elements, int k) {
    for (int i = k; i < elements.size(); i++) {
        java.util.Collections.swap(elements, i, k);
        getAllPermutations(result, elements, k + 1);
        java.util.Collections.swap(elements, k, i);
    }
    if (k == elements.size() - 1) {
        result.add(new ArrayList<Integer>(elements));
    }
}

然后迭代所有排列:

public double maxPossibleSum(ArrayList<Double[]> lists) {
    List<List<Integer>> allPermutations = getAllPermutations(3);
    double maxSum = Double.NEGATIVE_INFINITY;
    for (List<Integer> permutation : allPermutations) {
        double sum = 0;
        for (int i = 0; i < permutation.size(); i++) {
            Integer index = permutation.get(i);
            sum += lists.get(i)[index];
        }
        if (sum > maxSum) {
            maxSum = sum;
        }
    }
    return maxSum;
}