<p>The problem can be slightly generalized as follows: given a set <span class="math-container">$I\subseteq\{1,\dots,n\}$</span> and a set <span class="math-container">$S$</span> of lists of <span class="math-container">$n$</span>-tuples, find a permutation <span class="math-container">$\sigma:\{1,\dots,|I|\}\to I$</span>  such that each <span class="math-container">$l\in S$</span> is sorted according to the lexicographical preorder that compares the <span class="math-container">$\sigma(1)^\text{th}$</span> component, and then the <span class="math-container">$\sigma(2)^\text{th}$</span> component, ..., and finally the <span class="math-container">$\sigma(|I|)^\text{th}$</span>. I'll write <span class="math-container">$&lt;_\sigma$</span> for this lexicographical order.</p>

<p>This new problem is easily solvable by recursion: If <span class="math-container">$I=\emptyset$</span>, there is nothing to do. Otherwise, find some <span class="math-container">$i_0\in I$</span> such that in each <span class="math-container">$l\in S$</span>, the <span class="math-container">$i_0^\text{th}$</span> component are increasing (and if no such <span class="math-container">$i_0$</span> exist, return an error). Define <span class="math-container">$I':=I\setminus\{i_0\}$</span> and <span class="math-container">$S'$</span> the set of lists you get by splitting each list every time the <span class="math-container">$i_0^\text{th}$</span> component changes. A recursive call with <span class="math-container">$I'$</span> and <span class="math-container">$S'$</span> gives you a bijection <span class="math-container">$\sigma':\{1,\dots,|I|-1\}\to I'$</span> and you can then simply return <span class="math-container">$\sigma$</span> defined by <span class="math-container">$\sigma(1)=i_0$</span> and <span class="math-container">$\sigma(i+1)=\sigma'(i)$</span>.</p>

<p>This algorithm runs in <span class="math-container">$O(|I|^2 |S|)$</span> (where <span class="math-container">$|I|$</span> is the cardinal of <span class="math-container">$I$</span>, and <span class="math-container">$|S|=\sum\limits_{l\in S}\operatorname{length}(l)$</span>). In your case and with your notations, that would be <span class="math-container">$O(n^2N)$</span>.</p>

<p>I think that a slight variation of this algorithm runs in <span class="math-container">$O(|I||S|+|I|^2)$</span>. It is described at the end of this answers. The proofs concern the <span class="math-container">$O(|I|^2 |S|)$</span> version but should be (relatively) easy to adapt to the faster version.</p>

<hr>

<p><strong>Correctness</strong></p>

<p>The invariant is that if the algorithm returns a permutation <span class="math-container">$\sigma$</span>, then all the lists in <span class="math-container">$S$</span> are sorted according to <span class="math-container">$&lt;_\sigma$</span>.</p>

<p>The proof is by induction on <span class="math-container">$I$</span>. The base case is trivial because all lists are sorted according to the neutral element for the lexicographical product: equality.</p>

<p>In the inductive case, take any <span class="math-container">$l\in S$</span> we know that the sublists <span class="math-container">$l_1,\dots,l_r$</span> that resulted from splitting <span class="math-container">$l$</span> at the points where the <span class="math-container">$i_0^\text{th}$</span> component changed (i.e. <span class="math-container">$l=l_1@\dots@l_r$</span> where <span class="math-container">$@$</span> is concatenation, for each <span class="math-container">$k\in\{1,\dots,r\}$</span> all elements of <span class="math-container">$l_k$</span> have the same <span class="math-container">$i_0^\text{th}$</span> component, and for any <span class="math-container">$k\in\{1,\dots,r-1\}$</span> <span class="math-container">$(l_k.last)[i_0]\not=(l_{k+1}.first)[i_0]$</span>. Since we chose <span class="math-container">$i_0$</span> such that <span class="math-container">$l$</span> (and therefore <span class="math-container">$l_k$</span> for all <span class="math-container">$k\in\{1,\dots,r\}$</span>) is sorted with respect to <span class="math-container">$&lt;_{i_0}$</span>, this induces that (A) <span class="math-container">$a&lt;_{i_0}b$</span> iff <span class="math-container">$a\in l_k$</span> and <span class="math-container">$b\in l_{k'}$</span> with <span class="math-container">$k&lt;k'$</span>. By the induction hypothesis, (B) each <span class="math-container">$l_k$</span> is sorted with respect to <span class="math-container">$&lt;_{\sigma'}$</span>.</p>

<p>Let <span class="math-container">$a,b\in l$</span> such that <span class="math-container">$a$</span> appears before <span class="math-container">$b$</span> in <span class="math-container">$l$</span>.</p>

<ul>
<li><p>If <span class="math-container">$a$</span> and <span class="math-container">$b$</span> appear in the same <span class="math-container">$l_k$</span>, by (A), <span class="math-container">$a~_{i_0}b$</span> (i.e. <span class="math-container">$a\le_{i_0}b$</span> and <span class="math-container">$b\le_{i_0}a$</span>) and <span class="math-container">$a$</span> appears before <span class="math-container">$b$</span> in <span class="math-container">$l_k$</span> so that by (B) <span class="math-container">$a&lt;_{\sigma'}b$</span>. We therefore have <span class="math-container">$a(&lt;_{i_0}\times_\text{lex}&lt;_{\sigma'})b$</span>.</p></li>
<li><p>If <span class="math-container">$a$</span> appears in <span class="math-container">$l_k$</span> and <span class="math-container">$b$</span> appears in <span class="math-container">$l_{k'}$</span> with <span class="math-container">$k&lt;k'$</span>, then by (A), <span class="math-container">$a&lt;_{i_0}b$</span> and we therefore have <span class="math-container">$a(&lt;_{i_0}\times_\text{lex}&lt;_{\sigma'})b$</span>.</p></li>
</ul>

<p>We are done because <span class="math-container">$(&lt;_{i_0}\times_\text{lex}&lt;_{\sigma'})={&lt;_\sigma}$</span>.</p>

<p><strong>Completeness</strong></p>

<p>The invariant is that if every <span class="math-container">$l\in S$</span> is sorted according to some <span class="math-container">$&lt;_{\tilde\sigma}$</span> then the algorithm will return <span class="math-container">$\sigma$</span> such that for any <span class="math-container">$l\in S$</span> and <span class="math-container">$a,b\in l$</span>, <span class="math-container">$a&lt;_\sigma b$</span> iff <span class="math-container">$a&lt;_{\tilde\sigma}b$</span>. This implies that a list in <span class="math-container">$S$</span> being sorted with respect to <span class="math-container">$&lt;_\sigma$</span> is equivalent it being sorted with respect to <span class="math-container">$&lt;_{\tilde\sigma}$</span>. We prove this invariant by induction in <span class="math-container">$I$</span>. The base case is trivial.</p>

<p>In the inductive case, suppose that <span class="math-container">$l\in S$</span> is sorted according to some <span class="math-container">$&lt;_{\tilde\sigma}$</span>. Defined <span class="math-container">$\tilde\sigma':\{1,\dots,|I'|\}\to I'$</span> by <span class="math-container">$\tilde\sigma'(i)=\tilde\sigma(i)$</span> if <span class="math-container">$i&lt;i_0$</span> and <span class="math-container">$\tilde\sigma'(i)=\tilde\sigma(i-1)$</span> if <span class="math-container">$i&gt;i_0$</span>. Since each <span class="math-container">$l_k\in S'$</span> is sorted with respect to <span class="math-container">$\tilde\sigma$</span>, it is also sorted with respect to <span class="math-container">$\tilde\sigma'$</span>. By the induction hypothesis, we therefore have that for all <span class="math-container">$a,b\in l_k$</span>, <span class="math-container">$a&lt;_{\tilde\sigma'}b$</span> iff <span class="math-container">$a&lt;_{\sigma'}b$</span>.</p>

<p>Let <span class="math-container">$a,b \in l$</span>.</p>

<ul>
<li><p>If <span class="math-container">$a,b\in l_k$</span>, <span class="math-container">$a&lt;_{\tilde\sigma} b$</span> iff <span class="math-container">$a&lt;_{\tilde\sigma'}b$</span> iff <span class="math-container">$a&lt;_{\sigma'}b$</span> iff <span class="math-container">$a&lt;_{\sigma}$</span>.</p></li>
<li><p>If <span class="math-container">$a\in l_k$</span> and <span class="math-container">$b\in l_{k'}$</span> with <span class="math-container">$k&lt;k'$</span>, by (A), <span class="math-container">$a&lt;_{i_0} b$</span> and we therefore have <span class="math-container">$a&lt;_{\sigma}b$</span>. Since <span class="math-container">$l$</span> is sorted with respect to <span class="math-container">$&lt;_{\tilde\sigma}$</span>, <span class="math-container">$a&lt;_{\tilde\sigma}b$</span>. So we indeed have <span class="math-container">$a&lt;_{\tilde\sigma}b$</span> iff <span class="math-container">$a&lt;_{\sigma}b$</span> (because both are true).</p></li>
</ul>

<hr>

<p>We can boost it a bit by keeping keeping <span class="math-container">$S$</span> as a list (such that <span class="math-container">$L:=\operatorname{flatten}(S)$</span> is an invariant) instead of a set. You also keep a list <span class="math-container">$J$</span> of integers such that <span class="math-container">$\forall k\in\{1,\dots,|I|\}$</span>, the sublist <span class="math-container">$L[1\dots J[k]]$</span> is sorted according to <span class="math-container">$&lt;_k$</span>. Then, to test a candidate <span class="math-container">$i_0$</span>, you only check that <span class="math-container">$L[J[i_0]\dots |L|]$</span> is sorted with respect to <span class="math-container">$&lt;_{i_0}$</span> (where you would previously test that <span class="math-container">$L[1\dots |L|]$</span> is), and if it fails at some point, you update <span class="math-container">$J[i_0]$</span> to the greatest <span class="math-container">$j$</span> such that <span class="math-container">$L[1\dots j]$</span> is sorted according to <span class="math-container">$&lt;_{i_0}$</span>. The number of comparisons is then bounded by <span class="math-container">$O(|I||S|+|I|^2)$</span> because:</p>

<ul>
<li><p>You only get a positive answer for a test once (because then, you remember it was positive with <span class="math-container">$J$</span> and never test it again) which amounts for <span class="math-container">$O(|I||S|)$</span> because <span class="math-container">$\sum\limits_{1\le k \le |J|}J[k]$</span> starts at <span class="math-container">$0$</span>, increases by one after every positive test (if we update it after every comparison instead of just after a comparison with a negative answer), and is bounded by <span class="math-container">$\sum\limits_{1\le k \le |J|}|S|=|J||S|=|I||S|$</span>. </p></li>
<li><p>There are at most <span class="math-container">$O(|I|^2)$</span> negative answers, because <span class="math-container">$|I|$</span> strictly decreases at each iteration of the outer loop, and in the worst case, the right <span class="math-container">$i_0$</span> is the last you try.</p></li>
</ul>

<p>You could probably further optimize it by trying all possible <span class="math-container">$i_0$</span> in parallel, and picking one as soon as it's the only one left (instead of checking that the rest of the list is indeed sorted with respect to that index).</p>

CC BY-SA 4.0
2019-05-09T16:07:18.890Z
Clever!  Do you have a proof that this algorithm never gets stuck?  1. In your "find $i_0$" step, if there is no such $i_0$, then the algorithm needs to return "no permutation exists".  2. If you modify the algorithm in this way, do you have a proof that if the algorithm returns "no permutation exists" then it is correct?  In particular, suppose you choose $i_0, i_1, i_2, \dots,i_{k-1}$ and then when trying to find $i_k$ you can't find any and return "no permutation exists"; will this always be correct?  Why don't we need to backtrack and try other choices of $i_0,\dots,i_{k-1}$?
D.W.
CC BY-SA 4.0
2019-05-09T18:21:17.443Z
@D.W. I added stuff
xavierm02
CC BY-SA 4.0
2019-05-10T10:48:22.437Z
It seems to me that the original algorithm (at least naively) runs much slower, more like $\mathcal O((|I| - 1)!|S|)$. Suppose that $S$ contains elements whose first $|I|-1$ components are all always equal, and the final component is sorted in reverse order. Then you recursively try out every permutation of $\{1, \ldots, |I|-1\}$ before finding out that it does not lead to a solution.
Mees de Vries
CC BY-SA 4.0
2019-05-10T11:00:33.043Z
@MeesdeVries The algorithm decides if there is a $\sigma$ such that the list is ordered according to $<_\sigma$ and if so returns such a $\sigma$. In your example, it would build **one** arbitrary (because the order in which we test candidates for $i_0$ has not been specified) permutation (because all the orders $<_\sigma$ are equivalent for this list) and would fail to find $i_0$ at the last step when $|I|=1$, and would therefore return that no such permutation exists. The algorithm never needs to backtrack because if several $i_0$ are good candidate, swapping them doesn't change anything.
xavierm02
CC BY-SA 4.0
2019-05-09T12:39:36.410Z
2019-05-11T15:59:22.700Z
2019-05-11T15:59:22.700Z
xavierm02
<p>I think there's a better algorithm and I'll edit it into the accepted answer if I manager to get it to work properly but until then I'll leave it here:</p>

<p>Given a preorder <span class="math-container">$\le$</span>, we write:</p>

<ul>
<li><span class="math-container">$a\sim b$</span> for <span class="math-container">$a\le b$</span> and <span class="math-container">$b\le a$</span>;</li>
<li><span class="math-container">$a\lt b$</span> for <span class="math-container">$a\le b$</span> and not <span class="math-container">$b\le a$</span>.</li>
</ul>

<p>Given two preorders <span class="math-container">$\le_1$</span> and <span class="math-container">$\le_2$</span> on the same set <span class="math-container">$X$</span>, we write <span class="math-container">$\le_1 \&amp; \le_2$</span> for the preorder on <span class="math-container">$X$</span> defined by <span class="math-container">$a \left(\le_1 \&amp; \le_2\right) b$</span> iff <span class="math-container">$a\lt_1 b$</span> or <span class="math-container">$a\sim_1 b$</span> and <span class="math-container">$a\le_2 b$</span>.</p>

<p>This construction generalizes the lexicographical product of orders: Given orders <span class="math-container">$\le_1$</span> on <span class="math-container">$X_1$</span> and <span class="math-container">$\le_2$</span> on <span class="math-container">$X_2$</span>, let <span class="math-container">$\le_i'$</span> be the preorder on <span class="math-container">$X_1\times X_2$</span> defined by <span class="math-container">$(a_1,a_2)\le_i'(b_1,b_2)$</span> iff <span class="math-container">$a_i\le_i b_i$</span>. Then <span class="math-container">$(a_1,a_2)\mathrel{\left({\le_1}\times_\text{lex}{\le_2}\right)}(b_1,b_2)$</span> iff <span class="math-container">$(a_1,a_2)\mathrel{\left({\le_1'}\mathrel{\&amp;}{\le_2'}\right)}(b_1,b_2)$</span>.</p>

<p>Given a finite set <span class="math-container">$X$</span>, we call enumeration of <span class="math-container">$X$</span> a bijection <span class="math-container">$\sigma:\{1,\dots,|X|\}\to X$</span>. For an enumeration <span class="math-container">$\sigma$</span>, we write <span class="math-container">$|\sigma|$</span> for the cardinal of its codomain. Given an enumeration <span class="math-container">$\sigma$</span> of <span class="math-container">$I$</span> and for each <span class="math-container">$i\in I$</span> a preorder <span class="math-container">$\le_i$</span>, we write <span class="math-container">$\le_\sigma$</span> for the preorder <span class="math-container">${\le_{\sigma(1)}}\&amp;\dots\&amp; {\le_{\sigma(k)}}$</span>.</p>

<p>Given two enumerations, one of <span class="math-container">$I_1$</span> and one of <span class="math-container">$I_2$</span>, we define their concatenation <span class="math-container">$\sigma_1,\sigma_2$</span> by <span class="math-container">$(\sigma_1,\sigma_2)(k):=\sigma_1(k)$</span> if <span class="math-container">$k&lt;= k_1$</span> and <span class="math-container">$(\sigma_1,\sigma_2)(k):=\sigma_2(k-k_1)$</span> if <span class="math-container">$k&gt;k_1$</span>. Note that if <span class="math-container">$I_1\cap I_2=\emptyset$</span>, then <span class="math-container">$\sigma_1,\sigma_2$</span> is also an enumeration. We also write <span class="math-container">$\sigma_1,i$</span> for <span class="math-container">$\sigma_1,(1\mapsto i)$</span>. We say that <span class="math-container">$\sigma$</span> extends <span class="math-container">$\sigma_1$</span> if <span class="math-container">$\sigma=\sigma_1,\sigma_2$</span> for some <span class="math-container">$\sigma_2$</span>.</p>

<hr>

<p>The problem can be rephrased as:</p>

<ul>
<li>Input:

<ul>
<li>A set <span class="math-container">$X$</span>;</li>
<li>A list <span class="math-container">$L$</span> of elements of <span class="math-container">$X$</span>;</li>
<li>A set <span class="math-container">$I$</span> of indices, and for each <span class="math-container">$i\in I$</span>, a preorder <span class="math-container">$\le_i$</span> on <span class="math-container">$X$</span>;</li>
</ul></li>
<li>Output: an enumeration <span class="math-container">$\sigma$</span> of <span class="math-container">$I$</span> such that the list <span class="math-container">$L$</span> is sorted with respect to <span class="math-container">$\le_\sigma$</span>, or Error if no such enumeration exist.</li>
</ul>

<hr>

<p>We now generalize the problem to the following:</p>

<ul>
<li>Input:

<ul>
<li>A set <span class="math-container">$X$</span>;</li>
<li>A list <span class="math-container">$L$</span> of elements of <span class="math-container">$X$</span>;</li>
<li>A set <span class="math-container">$I$</span> of indices, and for each <span class="math-container">$i\in I$</span>, a preorder <span class="math-container">$\le_i$</span> on <span class="math-container">$X$</span>;</li>
<li>A subset <span class="math-container">$I_\text{todo}\subseteq I$</span> of indices. We write <span class="math-container">$I_\text{done}$</span> for <span class="math-container">$I\setminus I_\text{todo}$</span>;</li>
<li>An an enumeration <span class="math-container">$\sigma$</span> of <span class="math-container">$I_\text{done}$</span>;</li>
<li>A set <span class="math-container">$J\subseteq I_\text{todo}$</span>;</li>
<li>A set <span class="math-container">$P\subseteq \{1,\dots,|L|-1\}$</span> of positions and a function <span class="math-container">$f:P\to \{1,\dots,|I|\}$</span> such that for all <span class="math-container">$p\in P$</span>, and for <span class="math-container">$\sigma'=\sigma$</span> and for all <span class="math-container">$\sigma'$</span> that extends <span class="math-container">$\sigma,i$</span> for some <span class="math-container">$i\in J$</span>, <span class="math-container">$L[p]\le_{\sigma'(1),\dots,\sigma'(f(p))} L[p+1]$</span>;</li>
</ul></li>
<li>Output: a bijection <span class="math-container">$\sigma:\{1,\dots, |I|\} \to I$</span> that extends <span class="math-container">$\sigma,i$</span> for some <span class="math-container">$i\in J$</span> (or is equal to <span class="math-container">$\sigma$</span> in the case where <span class="math-container">$I_\text{todo}=\emptyset$</span>), and such that for all <span class="math-container">$p\in P,L[p]\le_{\sigma}L[p+1]$</span>, or Error if no such bijection exist.</li>
</ul>

<p>The intuition is that we have already compared (some components of) <span class="math-container">$L[p]$</span> and <span class="math-container">$L[p+1]$</span> for each <span class="math-container">$p \in P$</span> (and we use <span class="math-container">$f$</span> to remember at what information we gained) and that from those comparisons, we deduced that necessarily, any enumeration <span class="math-container">$\tilde\sigma$</span> of <span class="math-container">$I$</span> such that <span class="math-container">$L$</span> is sorted with respect to <span class="math-container">$&lt;_\tilde{\sigma}$</span> extends <span class="math-container">$\sigma,i$</span> for some <span class="math-container">$i\in J$</span>.</p>

<p>More precisely, we are building an enumeration of <span class="math-container">$I$</span> by assigning a index to <span class="math-container">$1$</span>, then to <span class="math-container">$2$</span> and so on until <span class="math-container">$|I|$</span>. <span class="math-container">$I_\text{done}$</span> is the set of indices that have already been placed in the numeration, <span class="math-container">$\sigma$</span> is the corresponding enumeration of <span class="math-container">$I_\text{done}$</span> and <span class="math-container">$I_\text{todo}$</span> is the set of indices still have to be added to the enumeration. <span class="math-container">$J$</span> is the set of candidate indices that could a priori be placed next in the enumeration. <span class="math-container">$P$</span> is the set of positions <span class="math-container">$p$</span> at which we have already done comparisons. If <span class="math-container">$f(p)=|I|$</span> then it means we never need to compare at that positions again. <span class="math-container">$f(p)&lt;|I|$</span> means that we had <span class="math-container">$L[p]\sim_\sigma L[p+1]$</span> last time we checked, we we used <span class="math-container">$f(p)$</span> to remember up to which component we checked.</p>

<p>Note that we get back the original problem by taking <span class="math-container">$I_\text{todo}:=I$</span>, <span class="math-container">$\sigma$</span> the bijection on the empty set, <span class="math-container">$J:=I$</span>, <span class="math-container">$P:=\emptyset$</span> and <span class="math-container">$f$</span> the bijection on the empty set.</p>

<p>This new problem is easy to solve recursively:</p>

<ul>
<li><p>If <span class="math-container">$P=\{1,\dots,|L|-1\}$</span>, return <span class="math-container">$\sigma,\sigma_J$</span> where <span class="math-container">$\sigma_J$</span> is any bijection <span class="math-container">$\{1,\dots,|J|\}\to J$</span>.</p></li>
<li><p>If <span class="math-container">$I_\text{todo}=\emptyset$</span>, return <span class="math-container">$\sigma$</span>.</p></li>
<li><p>If <span class="math-container">$J=\emptyset$</span>, return Error.</p></li>
<li><p>If <span class="math-container">$J=\{i_0\}$</span> is a singleton, recurse with <span class="math-container">$I_\text{todo}':=I_\text{todo}\setminus \{i_0\}$</span>, <span class="math-container">$J':=I_\text{todo}'$</span> and <span class="math-container">$\sigma':=\sigma,i_0$</span>.</p></li>
</ul>

<p>If none of the above cases apply, choose <span class="math-container">$p\in \{1,\dots,|L|-1\}$</span> and:</p>

<ul>
<li><p>(A) If <span class="math-container">$p\in P$</span> and <span class="math-container">$f(p)=|I_\text{done}|$</span>, recurse with <span class="math-container">$J':=\{i\in J / L[p] \le_i L[p+1]\}$</span> and <span class="math-container">$f(p)$</span> increased by <span class="math-container">$1$</span>.</p></li>
<li><p>(B) If <span class="math-container">$p\in P$</span> and <span class="math-container">$f(p)&lt;|I_\text{done}|$</span>, let <span class="math-container">$i:=\sigma(f(p)+1)$</span> and then:</p>

<ul>
<li>If <span class="math-container">$L[p] &lt;_i L[p+1]$</span> then recurse with <span class="math-container">$f(p)$</span> changed to <span class="math-container">$|I|$</span>.</li>
<li>If <span class="math-container">$L[p] \sim_i L[p+1]$</span> then recurse with <span class="math-container">$f(p)$</span> increased by <span class="math-container">$1$</span>.</li>
<li>If <span class="math-container">$L[p] &gt;_i L[p+1]$</span> then return Error.</li>
</ul></li>
<li><p>If <span class="math-container">$p\not\in P$</span>, set <span class="math-container">$P':=P\sqcup \{p\}$</span> do (B) with <span class="math-container">$i:=\sigma(1)$</span>.</p></li>
</ul>

CC BY-SA 4.0
2019-05-11T18:52:52.167Z
@DisplayName It'd be helpful if you could look at this algorithm and tell me if it's understandable. I think it's the optimal algorithm (modulo a good choice of heuristic for the "choose p" part).
xavierm02
CC BY-SA 4.0
2019-05-11T18:53:03.670Z
@D.W. It'd be helpful if you could look at this algorithm and tell me if it's understandable. I think it's the optimal algorithm (modulo a good choice of heuristic for the "choose p" part).
xavierm02
CC BY-SA 4.0
2019-05-11T19:46:51.547Z
(Just driving by.) Note that the "@username" notification only works when "username" is the author of the given post (here: you) or users that already contributed to the discussion (here: no one). If you want to ping DisplayName or D.W., you may do it e.g. in the comment thread below the question.
Emil Jeřábek
CC BY-SA 4.0
2019-05-11T15:58:36.747Z
2019-05-11T18:54:54.850Z
2019-05-11T18:54:54.850Z
xavierm02
<p>I have a sorted list of <span class="math-container">$N$</span> n-tuples, but I do not know exactly how they were sorted. The person who sorted them did so by lexicographically ordering some permutation least-to-greatest. For example, if I see the list [(53,10),(10,53)], I can conclude that they must have been swapping the elements before comparing them. If I see the list [(1,2,3),(10,20,0),(2,30,20)], I can conclude that they must have permuted the tuples so that the second element was first.</p>

<p>It takes <span class="math-container">$\log_2 n! \approx n \log_2 n$</span> bits to describe the permutation, and I would expect to discover one bit with every comparison. If that's true, then it seems like there could be a manageable algorithm for searching lists that have been sorted in an unknown way. What is the complexity of searching this kind of list? What algorithm might be able to achieve it?</p>

CC BY-SA 4.0
2019-05-09T02:06:09.563Z
So you're given $n$-tuples $x_1,\dots,x_N$, and the goal is to find a permutation $\sigma \in S_n$ such that $\sigma x_1, \dots, \sigma x_N$ is lexicographically sorted?
D.W.
CC BY-SA 4.0
2019-05-09T13:44:59.667Z
@D.W. The end goal is a binary search, and if the permutation was known a binary search would be easy, so yes finding out the permutation would count as a solution. Hopefully this can be done faster than $O(N)$ in the length of the list!
Display Name
CC BY-SA 4.0
2019-05-09T18:44:55.297Z
@DisplayName I doubt it can be done faster than $O(Nn\log n)$. You need $\Omega(N)$ just to check that a given $\sigma$ works.
xavierm02
CC BY-SA 4.0
2019-05-09T19:00:46.950Z
@xavierm02 If $n=2$ you can check a given $\sigma$ just by comparing a couple non-equal elements. The list is known in advance to be sorted, it is only up to us to determine how. Granted, if every element is equal except for one, you would need $O(N)$ time to find it in the worst case.
Display Name
<ds.algorithms>
Determining how n-tuples are sorted as you search them?
Display Name
# Determining how n-tuples are sorted as you search them?

(Asked by: username_0 on 2019-05-08)

I have a sorted list of $N$ n-tuples, but I do not know exactly how they were sorted. The person who sorted them did so by lexicographically ordering some permutation least-to-greatest. For example, if I see the list [(53,10),(10,53)], I can conclude that they must have been swapping the elements before comparing them. If I see the list [(1,2,3),(10,20,0),(2,30,20)], I can conclude that they must have permuted the tuples so that the second element was first.

It takes $\log\_2 n! \approx n \log\_2 n$ bits to describe the permutation, and I would expect to discover one bit with every comparison. If that's true, then it seems like there could be a manageable algorithm for searching lists that have been sorted in an unknown way. What is the complexity of searching this kind of list? What algorithm might be able to achieve it?

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: So you're given $n$-tuples $x_1,\dots,x_N$, and the goal is to find a permutation $\sigma \in S_n$ such that $\sigma x_1, \dots, \sigma x_N$ is lexicographically sorted?  
> **username_0**: @D.W. The end goal is a binary search, and if the permutation was known a binary search would be easy, so yes finding out the permutation would count as a solution. Hopefully this can be done faster than $O(N)$ in the length of the list!  
> **username_2**: @DisplayName I doubt it can be done faster than $O(Nn\log n)$. You need $\Omega(N)$ just to check that a given $\sigma$ works.  
> **username_0**: @xavierm02 If $n=2$ you can check a given $\sigma$ just by comparing a couple non-equal elements. The list is known in advance to be sorted, it is only up to us to determine how. Granted, if every element is equal except for one, you would need $O(N)$ time to find it in the worst case.  

---

## 2 answers

### Answer by username_2 on 2019-05-09. Score: 4 | Accepted answer

The problem can be slightly generalized as follows: given a set $I\subseteq\{1,\dots,n\}$ and a set $S$ of lists of $n$-tuples, find a permutation $\sigma:\{1,\dots,|I|\}\to I$ such that each $l\in S$ is sorted according to the lexicographical preorder that compares the $\sigma(1)^\text{th}$ component, and then the $\sigma(2)^\text{th}$ component, ..., and finally the $\sigma(|I|)^\text{th}$. I'll write $<\_\sigma$ for this lexicographical order.

This new problem is easily solvable by recursion: If $I=\emptyset$, there is nothing to do. Otherwise, find some $i\_0\in I$ such that in each $l\in S$, the $i\_0^\text{th}$ component are increasing (and if no such $i\_0$ exist, return an error). Define $I':=I\setminus\{i\_0\}$ and $S'$ the set of lists you get by splitting each list every time the $i\_0^\text{th}$ component changes. A recursive call with $I'$ and $S'$ gives you a bijection $\sigma':\{1,\dots,|I|-1\}\to I'$ and you can then simply return $\sigma$ defined by $\sigma(1)=i\_0$ and $\sigma(i+1)=\sigma'(i)$.

This algorithm runs in $O(|I|^2 |S|)$ (where $|I|$ is the cardinal of $I$, and $|S|=\sum\limits\_{l\in S}\operatorname{length}(l)$). In your case and with your notations, that would be $O(n^2N)$.

I think that a slight variation of this algorithm runs in $O(|I||S|+|I|^2)$. It is described at the end of this answers. The proofs concern the $O(|I|^2 |S|)$ version but should be (relatively) easy to adapt to the faster version.

---

**Correctness**

The invariant is that if the algorithm returns a permutation $\sigma$, then all the lists in $S$ are sorted according to $<\_\sigma$.

The proof is by induction on $I$. The base case is trivial because all lists are sorted according to the neutral element for the lexicographical product: equality.

In the inductive case, take any $l\in S$ we know that the sublists $l\_1,\dots,l\_r$ that resulted from splitting $l$ at the points where the $i\_0^\text{th}$ component changed (i.e. $l=l\_1@\dots@l\_r$ where $@$ is concatenation, for each $k\in\{1,\dots,r\}$ all elements of $l\_k$ have the same $i\_0^\text{th}$ component, and for any $k\in\{1,\dots,r-1\}$ $(l\_k.last)[i\_0]\not=(l\_{k+1}.first)[i\_0]$. Since we chose $i\_0$ such that $l$ (and therefore $l\_k$ for all $k\in\{1,\dots,r\}$) is sorted with respect to $<\_{i\_0}$, this induces that (A) $a<\_{i\_0}b$ iff $a\in l\_k$ and $b\in l\_{k'}$ with $k. By the induction hypothesis, (B) each $l\_k$ is sorted with respect to $<\_{\sigma'}$.

Let $a,b\in l$ such that $a$ appears before $b$ in $l$.

* If $a$ and $b$ appear in the same $l\_k$, by (A), $a~\_{i\_0}b$ (i.e. $a\le\_{i\_0}b$ and $b\le\_{i\_0}a$) and $a$ appears before $b$ in $l\_k$ so that by (B) $a<\_{\sigma'}b$. We therefore have $a(<\_{i\_0}\times\_\text{lex}<\_{\sigma'})b$.
* If $a$ appears in $l\_k$ and $b$ appears in $l\_{k'}$ with $k, then by (A), $a<\_{i\_0}b$ and we therefore have $a(<\_{i\_0}\times\_\text{lex}<\_{\sigma'})b$.

We are done because $(<\_{i\_0}\times\_\text{lex}<\_{\sigma'})={<\_\sigma}$.

**Completeness**

The invariant is that if every $l\in S$ is sorted according to some $<\_{\tilde\sigma}$ then the algorithm will return $\sigma$ such that for any $l\in S$ and $a,b\in l$, $a<\_\sigma b$ iff $a<\_{\tilde\sigma}b$. This implies that a list in $S$ being sorted with respect to $<\_\sigma$ is equivalent it being sorted with respect to $<\_{\tilde\sigma}$. We prove this invariant by induction in $I$. The base case is trivial.

In the inductive case, suppose that $l\in S$ is sorted according to some $<\_{\tilde\sigma}$. Defined $\tilde\sigma':\{1,\dots,|I'|\}\to I'$ by $\tilde\sigma'(i)=\tilde\sigma(i)$ if $i and $\tilde\sigma'(i)=\tilde\sigma(i-1)$ if $i>i\_0$. Since each $l\_k\in S'$ is sorted with respect to $\tilde\sigma$, it is also sorted with respect to $\tilde\sigma'$. By the induction hypothesis, we therefore have that for all $a,b\in l\_k$, $a<\_{\tilde\sigma'}b$ iff $a<\_{\sigma'}b$.

Let $a,b \in l$.

* If $a,b\in l\_k$, $a<\_{\tilde\sigma} b$ iff $a<\_{\tilde\sigma'}b$ iff $a<\_{\sigma'}b$ iff $a<\_{\sigma}$.
* If $a\in l\_k$ and $b\in l\_{k'}$ with $k, by (A), $a<\_{i\_0} b$ and we therefore have $a<\_{\sigma}b$. Since $l$ is sorted with respect to $<\_{\tilde\sigma}$, $a<\_{\tilde\sigma}b$. So we indeed have $a<\_{\tilde\sigma}b$ iff $a<\_{\sigma}b$ (because both are true).

---

We can boost it a bit by keeping keeping $S$ as a list (such that $L:=\operatorname{flatten}(S)$ is an invariant) instead of a set. You also keep a list $J$ of integers such that $\forall k\in\{1,\dots,|I|\}$, the sublist $L[1\dots J[k]]$ is sorted according to $<\_k$. Then, to test a candidate $i\_0$, you only check that $L[J[i\_0]\dots |L|]$ is sorted with respect to $<\_{i\_0}$ (where you would previously test that $L[1\dots |L|]$ is), and if it fails at some point, you update $J[i\_0]$ to the greatest $j$ such that $L[1\dots j]$ is sorted according to $<\_{i\_0}$. The number of comparisons is then bounded by $O(|I||S|+|I|^2)$ because:

* You only get a positive answer for a test once (because then, you remember it was positive with $J$ and never test it again) which amounts for $O(|I||S|)$ because $\sum\limits\_{1\le k \le |J|}J[k]$ starts at $0$, increases by one after every positive test (if we update it after every comparison instead of just after a comparison with a negative answer), and is bounded by $\sum\limits\_{1\le k \le |J|}|S|=|J||S|=|I||S|$.
* There are at most $O(|I|^2)$ negative answers, because $|I|$ strictly decreases at each iteration of the outer loop, and in the worst case, the right $i\_0$ is the last you try.

You could probably further optimize it by trying all possible $i\_0$ in parallel, and picking one as soon as it's the only one left (instead of checking that the rest of the list is indeed sorted with respect to that index).

> **Comments:**
> **username_1**: Clever!  Do you have a proof that this algorithm never gets stuck?  1. In your "find $i_0$" step, if there is no such $i_0$, then the algorithm needs to return "no permutation exists".  2. If you modify the algorithm in this way, do you have a proof that if the algorithm returns "no permutation exists" then it is correct?  In particular, suppose you choose $i_0, i_1, i_2, \dots,i_{k-1}$ and then when trying to find $i_k$ you can't find any and return "no permutation exists"; will this always be correct?  Why don't we need to backtrack and try other choices of $i_0,\dots,i_{k-1}$?  
> **username_2**: @D.W. I added stuff  
> **username_3**: It seems to me that the original algorithm (at least naively) runs much slower, more like $\mathcal O((|I| - 1)!|S|)$. Suppose that $S$ contains elements whose first $|I|-1$ components are all always equal, and the final component is sorted in reverse order. Then you recursively try out every permutation of $\{1, \ldots, |I|-1\}$ before finding out that it does not lead to a solution.  
> **username_2**: @MeesdeVries The algorithm decides if there is a $\sigma$ such that the list is ordered according to $<_\sigma$ and if so returns such a $\sigma$. In your example, it would build **one** arbitrary (because the order in which we test candidates for $i_0$ has not been specified) permutation (because all the orders $<_\sigma$ are equivalent for this list) and would fail to find $i_0$ at the last step when $|I|=1$, and would therefore return that no such permutation exists. The algorithm never needs to backtrack because if several $i_0$ are good candidate, swapping them doesn't change anything.  

---

### Answer by username_2 on 2019-05-11. Score: 1

I think there's a better algorithm and I'll edit it into the accepted answer if I manager to get it to work properly but until then I'll leave it here:

Given a preorder $\le$, we write:

* $a\sim b$ for $a\le b$ and $b\le a$;
* $a\lt b$ for $a\le b$ and not $b\le a$.

Given two preorders $\le\_1$ and $\le\_2$ on the same set $X$, we write $\le\_1 \& \le\_2$ for the preorder on $X$ defined by $a \left(\le\_1 \& \le\_2\right) b$ iff $a\lt\_1 b$ or $a\sim\_1 b$ and $a\le\_2 b$.

This construction generalizes the lexicographical product of orders: Given orders $\le\_1$ on $X\_1$ and $\le\_2$ on $X\_2$, let $\le\_i'$ be the preorder on $X\_1\times X\_2$ defined by $(a\_1,a\_2)\le\_i'(b\_1,b\_2)$ iff $a\_i\le\_i b\_i$. Then $(a\_1,a\_2)\mathrel{\left({\le\_1}\times\_\text{lex}{\le\_2}\right)}(b\_1,b\_2)$ iff $(a\_1,a\_2)\mathrel{\left({\le\_1'}\mathrel{\&}{\le\_2'}\right)}(b\_1,b\_2)$.

Given a finite set $X$, we call enumeration of $X$ a bijection $\sigma:\{1,\dots,|X|\}\to X$. For an enumeration $\sigma$, we write $|\sigma|$ for the cardinal of its codomain. Given an enumeration $\sigma$ of $I$ and for each $i\in I$ a preorder $\le\_i$, we write $\le\_\sigma$ for the preorder ${\le\_{\sigma(1)}}\&\dots\& {\le\_{\sigma(k)}}$.

Given two enumerations, one of $I\_1$ and one of $I\_2$, we define their concatenation $\sigma\_1,\sigma\_2$ by $(\sigma\_1,\sigma\_2)(k):=\sigma\_1(k)$ if $k<= k\_1$ and $(\sigma\_1,\sigma\_2)(k):=\sigma\_2(k-k\_1)$ if $k>k\_1$. Note that if $I\_1\cap I\_2=\emptyset$, then $\sigma\_1,\sigma\_2$ is also an enumeration. We also write $\sigma\_1,i$ for $\sigma\_1,(1\mapsto i)$. We say that $\sigma$ extends $\sigma\_1$ if $\sigma=\sigma\_1,\sigma\_2$ for some $\sigma\_2$.

---

The problem can be rephrased as:

* Input:
  + A set $X$;
  + A list $L$ of elements of $X$;
  + A set $I$ of indices, and for each $i\in I$, a preorder $\le\_i$ on $X$;
* Output: an enumeration $\sigma$ of $I$ such that the list $L$ is sorted with respect to $\le\_\sigma$, or Error if no such enumeration exist.

---

We now generalize the problem to the following:

* Input:
  + A set $X$;
  + A list $L$ of elements of $X$;
  + A set $I$ of indices, and for each $i\in I$, a preorder $\le\_i$ on $X$;
  + A subset $I\_\text{todo}\subseteq I$ of indices. We write $I\_\text{done}$ for $I\setminus I\_\text{todo}$;
  + An an enumeration $\sigma$ of $I\_\text{done}$;
  + A set $J\subseteq I\_\text{todo}$;
  + A set $P\subseteq \{1,\dots,|L|-1\}$ of positions and a function $f:P\to \{1,\dots,|I|\}$ such that for all $p\in P$, and for $\sigma'=\sigma$ and for all $\sigma'$ that extends $\sigma,i$ for some $i\in J$, $L[p]\le\_{\sigma'(1),\dots,\sigma'(f(p))} L[p+1]$;
* Output: a bijection $\sigma:\{1,\dots, |I|\} \to I$ that extends $\sigma,i$ for some $i\in J$ (or is equal to $\sigma$ in the case where $I\_\text{todo}=\emptyset$), and such that for all $p\in P,L[p]\le\_{\sigma}L[p+1]$, or Error if no such bijection exist.

The intuition is that we have already compared (some components of) $L[p]$ and $L[p+1]$ for each $p \in P$ (and we use $f$ to remember at what information we gained) and that from those comparisons, we deduced that necessarily, any enumeration $\tilde\sigma$ of $I$ such that $L$ is sorted with respect to $<\_\tilde{\sigma}$ extends $\sigma,i$ for some $i\in J$.

More precisely, we are building an enumeration of $I$ by assigning a index to $1$, then to $2$ and so on until $|I|$. $I\_\text{done}$ is the set of indices that have already been placed in the numeration, $\sigma$ is the corresponding enumeration of $I\_\text{done}$ and $I\_\text{todo}$ is the set of indices still have to be added to the enumeration. $J$ is the set of candidate indices that could a priori be placed next in the enumeration. $P$ is the set of positions $p$ at which we have already done comparisons. If $f(p)=|I|$ then it means we never need to compare at that positions again. $f(p)<|I|$ means that we had $L[p]\sim\_\sigma L[p+1]$ last time we checked, we we used $f(p)$ to remember up to which component we checked.

Note that we get back the original problem by taking $I\_\text{todo}:=I$, $\sigma$ the bijection on the empty set, $J:=I$, $P:=\emptyset$ and $f$ the bijection on the empty set.

This new problem is easy to solve recursively:

* If $P=\{1,\dots,|L|-1\}$, return $\sigma,\sigma\_J$ where $\sigma\_J$ is any bijection $\{1,\dots,|J|\}\to J$.
* If $I\_\text{todo}=\emptyset$, return $\sigma$.
* If $J=\emptyset$, return Error.
* If $J=\{i\_0\}$ is a singleton, recurse with $I\_\text{todo}':=I\_\text{todo}\setminus \{i\_0\}$, $J':=I\_\text{todo}'$ and $\sigma':=\sigma,i\_0$.

If none of the above cases apply, choose $p\in \{1,\dots,|L|-1\}$ and:

* (A) If $p\in P$ and $f(p)=|I\_\text{done}|$, recurse with $J':=\{i\in J / L[p] \le\_i L[p+1]\}$ and $f(p)$ increased by $1$.
* (B) If $p\in P$ and $f(p)<|I\_\text{done}|$, let $i:=\sigma(f(p)+1)$ and then:

  + If $L[p] <\_i L[p+1]$ then recurse with $f(p)$ changed to $|I|$.
  + If $L[p] \sim\_i L[p+1]$ then recurse with $f(p)$ increased by $1$.
  + If $L[p] >\_i L[p+1]$ then return Error.
* If $p\not\in P$, set $P':=P\sqcup \{p\}$ do (B) with $i:=\sigma(1)$.

> **Comments:**
> **username_2**: @DisplayName It'd be helpful if you could look at this algorithm and tell me if it's understandable. I think it's the optimal algorithm (modulo a good choice of heuristic for the "choose p" part).  
> **username_2**: @D.W. It'd be helpful if you could look at this algorithm and tell me if it's understandable. I think it's the optimal algorithm (modulo a good choice of heuristic for the "choose p" part).  
> **username_4**: (Just driving by.) Note that the "@username" notification only works when "username" is the author of the given post (here: you) or users that already contributed to the discussion (here: no one). If you want to ping DisplayName or D.W., you may do it e.g. in the comment thread below the question.  

---

