1
$\begingroup$

Thanks to anon for contributing this wording:

Every permutation $\pi:\{1,\cdots,n\}\to\{1,\cdots,n\}$ induces an $n\times n$ array $A(\pi)$ of the absolute differences, whose $ij$ entry is $|\pi(i)-\pi(j)|$. I want an algorithm which takes as input a (possibly only-partially-filled in) $n\times n$ array $D$, and outputs a permutation $\pi$ that maximizes the number of entries common to both $D$ and $A(\pi)$.



Wording I can follow:

I'm looking for an algorythm that yields a permutation $P$ of the given set $L$.

Where $P$ minimally violates a given set of constraints $C$.

Where constraints $C$ each specify an absolute offsets for the indexes of a pair of elements of $L$.

For example:

Where:

$L = \{w, x, y, z\}\\C = \{\{w, x, 2\}, \{y, w, 1\}, \{y, z, 2\}\}$

Then a valid answer would be $P = \{w, y, x, z\}$

Because, as described in $C$:

$w$ and $x$ are now $2$ "index positions" apart.

$y$ and $w$ are neigbours at $1$ apart.

$y$ and $z$ also being $2$ apart.


The data for $C$ may contain contradictions, therefore the result may be an estimate.

Q: What is a good way to solve this?



I wondered about an approach where $L$ values are placed randomly along a 1D line. $C$ describing the end connections and rest length of connecting springs. Simulated until at rest. Could this produce a reasonably accurate result?

What other aproaches are recommended for finding $P$ from $L$ and $C$?

$\endgroup$
  • $\begingroup$ @Gilles is this a standard problem? $\endgroup$ – babou Jul 25 '15 at 21:11
1
$\begingroup$

Apparently, we're given a collection of equations of the form

$$|x_i - x_j| = c_{i,j},$$

where the $c_{i,j}$ are given and $x_1,\dots,x_n$ are the unknowns to solve for. We want to look for a valid solution that satisfies all of the equations, and where the values of $x_1,\dots,x_n$ are a permutation of $1,2,\dots,n$.

The kind of algorithm to use will probably depend upon how many equations we're given and the structure of the corresponding graph. However, here is a simple case to start with, to give you some intuition:

Suppose that we are given a complete set of $n(n-1)/2$ equations: i.e., for all $i,j$, we are given $c_{i,j}$. Then there is a polynomial-time algorithm to recover the $x_i$'s. Basically, we'll leave $x_1$ as a variable, and we'll try to express every other $x_i$ in terms of $x_1$. Define $\delta_i$ so that $x_i = x_1 + \delta_i$. Here's how the algorithm works:

  1. Guess $\delta_2$. Note that it is either $c_{1,2}$ or $-c_{1,2}$, so there are only two possibilities.

  2. Guess $\delta_3$. Again, there are only two possibilities: $c_{1,3}$ or $-c_{1,3}$.

  3. Check that $|\delta_2-\delta_3| = c_{2,3}$; if this doesn't hold, discard your current guess. (This will eliminate $1/2$ of the wrong guesses.)

  4. Guess $\delta_4$; there are only two possibilities.

  5. Check that $|\delta_2-\delta_4| = c_{2,4}$ and $|\delta_3-\delta_4|=c_{3,4}$; if either doesn't hold, discard the current guess. (This will eliminate at least $1/2$ of the wrong guesses.)

  6. Continue in this way, alternately guessing $\delta_i$ and then checking the equations $|\delta_j-\delta_i|=c_{j,i}$ hold for all $j=2,3,\dots,i-1$.

What's the running time? The expected running time to list all possible combinations for $\delta_2,\dots,\delta_n$ is $O(n)$. In particular, at each step, we double the number of combinations we need to consider (since there are two possibilities for the guess), but then we halve the number of combinations we need to consider (since $1/2$ of the wrong guesses can be discarded by virtue of the fact that they violate at least one of the known equations). Thus the expected number of guesses that remain at the $i$th step is a constant independent of $i$, which implies the running time bound above.

Finally, once you have a combination $\delta_2,\dots,\delta_n$, you can test whether it leads to a viable solution by checking all possible values of $x_1$, inferring the implied values of $x_2,\dots,x_n$ (using the known values for $\delta_2,\dots,\delta_n$), and then checking whether they are a permutation of $1,2,\dots,n$. Each combination takes $O(n^2)$ time to check, so the overall running time of the algorithm is $O(n^2)$. This can probably be reduced further, but it's enough to make it already a polynomial-time algorithm.

Now what if we're not given all of the equations? Then we can apply a similar strategy, but the running time will depend upon the number of equations we're given and the structure of the graph they correspond to. There's also some degree of freedom in the order that you guess $\delta_i$ values; it's not clear what the optimal strategy is, but probably it will involve looking for small highly-connected regions of the graph and starting with them first. The best approach might depend upon the specific distribution on problem instances that arises in your practical setting.

| cite | improve this answer | |
$\endgroup$

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.