3
$\begingroup$

Given two sorted arrays of floating point numbers $X$ and $Y$, we can define the S-distance as follows. The S-distance is defined as the minimum cost associated with the transformation of one point pattern $X$ into a pattern $Y$ by deleting, adding, and moving points (that is adding a constant to all points). The cost of a transformation is:

$$p_d|X_{delete}| + p_a|X_{add}| + p_m d$$

where $p_a$, $p_d$ and $p_m$ are parameters and $X_{delete}$ and $X_{add}$ are subsets of $X$ that are deleted and added. $|X_{delete}|$, for example, is the number of elements in $|X_{delete}|$ and not the sum of the values. $d$ is the value that we are adding to all the points in the sequence $X$.

For example, say $X = (1,2,3)$ and $Y = (2,4)$ then one possible transformation of $X$ into $Y$ has cost $p_d + p_m$ as we can delete $2$ from $X$ and then increase both the points in $X$ by $1$ to make $(2,4)$ (so $d = 1$).

By adding a point I mean inserting a new point into the array.

I am trying to work out what the complexity of computing this distance is. It is not obvious to me how to do this by dynamic programming for example.


@Gassa gives a solution using $O(n^2)$ hash function calls. Is there a simple dynamic programming (or other) solution that doesn't require any hash function calls at all?

$\endgroup$
  • 1
    $\begingroup$ Gassa's answer already describes how to do it without any hash functions: "use tree sets and tree maps, respectively [in place of hash sets and hash maps]". So it seems like your revised question has already been answered and your bounty conditions have already been achieved. (That said, it's not clear to me why one would need to avoid hashing.) $\endgroup$ – D.W. Jul 1 '18 at 18:33
  • $\begingroup$ @D.W. It's not $O(n^2)$ time if you use "tree sets and tree maps". $\endgroup$ – Anush Jul 1 '18 at 19:24
  • 1
    $\begingroup$ Nonetheless, it is $O(n^2 \log n)$ time, which is often pretty close for practical purposes. (see, e.g., cs.stackexchange.com/q/57814/755.) And if you care about the difference between $O(n^2 \log n)$ vs $O(n^2)$ it seems hard to understand why one would also forbid solutions that involve hashing. $\endgroup$ – D.W. Jul 1 '18 at 19:33
  • $\begingroup$ @D.W. Right. I am interested in an $O(n^2)$ solution without the extra log factor. Ideally this would be $O(n^2)$ worst case. $\endgroup$ – Anush Jul 1 '18 at 19:46
  • 1
    $\begingroup$ @Gassa That sounds great and now reminds me of 3 Sum. $\endgroup$ – Anush Jul 2 '18 at 6:12
3
$\begingroup$

Here's a start: an upper bound is $O(n^3)$.

Note that we need either $0$ or $1$ moves: any two moves could be expressed as one. Furthermore, this one move is commutative with all other operations: it may occur at any point in time, the end result will still be the same.

Barring some degenerate cases, consider one point $X_i$ which does not get deleted and moves into $Y_j$. There are a total of $n^2$ such possibilities. For each fixed $i$ and $j$, first, we know whether we need a move, and second, for all other points, we can establish which $X_u$ move into which $Y_v$ in $O(n)$. For example, put all $Y_v$ in a hash table in $O(n)$, iterate over all $X_u$ and search for them in the hash table in $O(n)$ total.


Here's a speedup to $O(n^2)$.

Consider all possible $n^2$ move distances: each "$X_i$ to $Y_j$" produces a distance. Some of the distances may turn out to be the same. In your example of $X = (1, 2, 3)$ and $Y = (2, 4)$, the $X_1 \to Y_1$ and $X_3 \to Y_2$ produce the same distance of $2$. So, in the end, each distance will have several pairs associated with it.

Now, we will need all $X_i$ to be different, and all $Y_j$ to be different. Then, if a distance $d$ has $r$ pairs associated with it, all $X_i$ in these pairs are pairwise different, and all $Y_j$ in these pairs are also pairwise different. It means that, when we move points by distance $d$, we will have $r$ matching points, and all other points will be non-matching, so will have to be deleted from $\{X\}$ or inserted into $\{Y\}$, respectively.

So, implementation-wise, maintain a hash map which maps a distance to the number of times we encountered such distance. Iterate over all pairs of "$X_i$ to $Y_j$" and fill the map, in $O(n^2)$ total. Now iterate the map and find the minimum cost, also in $O(n^2)$ total. For a distance $d$, when the number of pairs with such distance is $r (d)$, the cost is the sum of the following:

  • $p_m$ if $d$ is nonzero, or $0$ if $d$ is zero;
  • $p_d \cdot (l_X - r (d))$, where $l_X$ is the length of $\{X\}$;
  • $p_a \cdot (l_Y - r (d))$, where $l_Y$ is the length of $\{Y\}$.

It may be possible to handle the case when the sequences can contain equal elements, but the details look cumbersome.


All this assumes $O(1)$ performance of hash sets and hash maps. If that is a problem, at the very least, we can add logarithms and use tree sets and tree maps, respectively.

Also, the solution does not address precision loss for floating point operations. For example, the implementation may use integers, by multiplying the given floating point values values by a constant.

$\endgroup$
  • $\begingroup$ Thank you for this. In the second part of the algorithm, we iterate over all $O(n^2)$ different distances that were found. For each one we know how many times it occurs. For each such distance $\ell$ we will try adding $\ell$ to all the points in $X$, if I understand you correctly. Is that right? $\endgroup$ – Anush Jun 28 '18 at 20:04
  • 1
    $\begingroup$ @Anush Right. Then some will turn into $Y$s, and the others must be removed, and the remaining $Y$s must be added. In any order. $\endgroup$ – Gassa Jun 28 '18 at 20:46
  • 1
    $\begingroup$ Seems hashing is not necessary. A simple merge and scan is enough. $\endgroup$ – xskxzr Jun 29 '18 at 10:36
  • $\begingroup$ @xskxzr Could you say a little more about that observation please? $\endgroup$ – Anush Jun 30 '18 at 5:17
  • $\begingroup$ @xskxzr Hmm, I see what you mean for the $O(n^3)$ approach: for a fixed distance $d$, visit all $X$s and all values $Y_j + d$, similarly to how we would merge two sorted lists. But I don't yet see how to apply it for the $O(n^2)$ approach. $\endgroup$ – Gassa Jun 30 '18 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.