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)$.New wording: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 approach should work with data for $C$ that is generally consistent but has some noise and contradiction. The result may be an estimate.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$?Is there a closed form equation that will calculate $P$ from $L$ and $C$?Early wording:$s = \{A, B, C, D\}$ is an example set, and so is unordered.The elements of lists however have positions.Position 0 being the first, position 1 being the second, etc...Given information about the desired distances between the positions of elements, for example:$$\begin{align*}\text{position of }C &= (\text{position of }A) \pm 2\\\text{position of }B &= (\text{position of }C) \pm 1\\\text{position of }A &= (\text{position of }D) \pm 3\\\dots \end{align*}$$The order can be calculated, to yield a list.$(A, B, C, D)$That now has as order, $A$ then $B$, then $C$, then $D$. $A$ being element $0$, $B$ being element $1$, $C$ being element $2$ and $D$ being element $3$.However, what if the data is messier, generally having an order but containing noise and contradictions.What is a good way to solve this?Does using a physical anology of springs of different lengths, work well for this, and still work well in 1 dimension?C is connected to A with a spring of length 2B is connected to C with a spring of length 1A is connected to D with a spring if length 3ect...Is there a less iterative approach than this for calculating the answer, or a reasonable estimation?
Pairs distance to ordering?
algorithms;data structures;partial order