Java -有效地比较两组对象

Question

我有两组对象，每组由4个对象组成。目标是计算这两组之间的相似程度。两个对象之间的比较结果是一个整型数。这个数字越小，表示对象越相似。这些对象在组内的顺序与组的相等性无关。

所以我必须做的是比较组1的每个对象和组2的每个对象，这将给我16个不同的对象之间的比较结果。我将这些存储在4x4 int表中，称为costs。

int[][] costs= new int[4][4];
for(int i=0;i<4;i++){
     for(int j=0;j<4;j++){
         costs[i][j]=compare(objectGroup1[i],objectGroup2[j]);
      }
 }

现在我有4组4个比较结果，我必须从每组中选择一个结果，以便将它们相加并计算组之间的总距离度量。这就是我被困住的地方。我必须尝试4的所有组合并得到最小的和，但是有一个对象只能使用一次的限制。

示例:如果要添加的四个值中的第一个是objectGroup1[1]与objectGroup2[1]之间的比较结果，那么我不能在这四个值中使用使用objectGroup1[1]的任何其他比较结果，objectGroup2[1]也是如此。

有效示例:group1[1]-group2[2]， group1[2]-group2[1]， group1[3]-group2[3]，group1[4]-group2[4]---->每个组中的每个对象只出现一次

我在这里可以使用哪种算法?

Answer 1

听起来你是在试图找到第1组物品的排列，使其在配对时与第2组物品最相似。

Eric Lippert有一系列关于产生排列的博文。所以基本上你所要做的就是遍历它们，通过配对项来计算分数，然后返回最好的分数。基本上就是zip和MinBy-ing:

groupSimilarity =
    item1.Groups
    // (you have to implement Permutations)
    .Permutations()
    // we want to compute the best score, but we don't know which permutation will win
    // so we MinBy a function computing the permutation's score
    .MinBy(permutation =>
        // pair up the items and combine them, using the Similarity function
        permutation.Zip(item2.Groups, SimilarityFunction)
        // add up the similarity scores
        .Sum()
     )

上面的代码是c#，用"Linqy"函数风格写的(如果你不熟悉的话，很抱歉)。MinBy是MoreLinq的一个有用的函数，Zip是一个标准的Linq操作符。