Distance measure between two sets of possibly different size

I have 2 sets of integers, A and B, not necessarily of the same size. For my needs, I take the distance between each 2 elements a and b (integers) to be just abs(a-b).

I am defining the distance between the two sets as follows:

  1. If the sets are of the same size, minimize the sum of distances of all pairs [a,b] (a from A and b from B), minimization over all possible 'pairs partitions' (there are n! possible partitions).
  2. If the sets are not of the same size, let's say A of size m and B of size n, with m < n, then minimize the distance from (1) over all subsets of B which are of size m.

My question is, is the following algorithm (just an intuitive guess) gives the right answer, according to the definition written above.

  • Construct a matrix D of size m X n, with D(i,j) = abs(A(i)-B(j))
  • Find the smallest element of D, accumulate it, and delete the row and the column of that element. Accumulate the next smallest entry, and keep accumulating until all rows and columns are deleted.

for example, if A={0,1,4} and B={3,4}, then D is (with the elements above and to the left):

3 4

0 3 4

1 2 3

4 1 0

And the distance is 0 + 2 = 2, coming from pairing 4 with 4 and 3 with 1.

5
задан Itamar Katz 14 December 2010 в 16:46
поделиться