1

I have two groups of objects where each group consists of 4 objects. The goal is to compute the degree of similarity between thes two groups. The comparison between two objects results to an int number. The lowest this number is the more similar the objects are. The order of these objects withing the group doesn't matter to the group equality.

So what i must do is compare each object of group 1 with each object of group 2 and this will give me 16 different comparison result between objects. I store these in a 4x4 int table called 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]);
      }
 }

Now i have 4 sets of 4 comparison results and I must choose one result from each set, in order to add them and compute the total distance metric between the groups. This is the point where i got stuck. I must try all combinations of four and get the minimum sum but there is the restrition of using an object only once.

Example: if the first of four values to add is the comparison result between objectGroup1[1] - objectGroup2[1] then I can't use in this foursome any other comparison results that came using objectGroup1[1] and same goes for objectGroup2[1].

valid example: group1[1]-group2[2], group1[2]-group2[1], group1[3]-group2[3],group1[4]-group2[4]---->each object from each group appears only once

What kind of algorithm can I use here?

Anonymous
  • 4,470
  • 3
  • 36
  • 67

1 Answers1

0

It sounds like you're trying to find the permutation of group 1's items that make it most similar to group 2's items when pairing the items off.

Eric Lippert has a good series of blog posts on producing permutations. So basically all you have to do is iterate over them, computing the score by pairing items, and return the best score. Basically just Zip-ing and 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()
     )

The above code is C#, written in a "Linqy" functional style (sorry if you're not familiar with that). MinBy is a useful function from MoreLinq, Zip is a standard Linq operator.

Community
  • 1
  • 1
Craig Gidney
  • 17,763
  • 5
  • 68
  • 136
  • if i'm not mistaking permutation refers to the distinct rearrangement of the objects of 1 group. What i'm looking for is the distinct combinations between two different sets of objects. correct me if i'm wrong – Anonymous Jul 17 '14 at 18:45
  • 1
    You only need to permute one of them to get all of the matchings-that-don't-repeat-an-object. If you permute both, you just end up repeating matchings. For example, {1,2} vs {3,4} has two possible matchings: {1:3, 2:4} and {2:3, 1:4}. Including {1:4, 2:3} and {2:4, 1:3} as well just repeats two matchings that are already there. – Craig Gidney Jul 17 '14 at 19:10