Determining how n-tuples are sorted as you search them? 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?
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 $&lt;_\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 $&lt;_\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 $&lt;_{i_0}$, this induces that (A) $a&lt;_{i_0}b$ iff $a\in l_k$ and $b\in l_{k'}$ with $k&lt;k'$. By the induction hypothesis, (B) each $l_k$ is sorted with respect to $&lt;_{\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&lt;_{\sigma'}b$. We therefore have $a(&lt;_{i_0}\times_\text{lex}&lt;_{\sigma'})b$.
If $a$ appears in $l_k$ and $b$ appears in $l_{k'}$ with $k&lt;k'$, then by (A), $a&lt;_{i_0}b$ and we therefore have $a(&lt;_{i_0}\times_\text{lex}&lt;_{\sigma'})b$.


We are done because $(&lt;_{i_0}\times_\text{lex}&lt;_{\sigma'})={&lt;_\sigma}$.

Completeness

The invariant is that if every $l\in S$ is sorted according to some $&lt;_{\tilde\sigma}$ then the algorithm will return $\sigma$ such that for any $l\in S$ and $a,b\in l$, $a&lt;_\sigma b$ iff $a&lt;_{\tilde\sigma}b$. This implies that a list in $S$ being sorted with respect to $&lt;_\sigma$ is equivalent it being sorted with respect to $&lt;_{\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 $&lt;_{\tilde\sigma}$. Defined $\tilde\sigma':\{1,\dots,|I'|\}\to I'$ by $\tilde\sigma'(i)=\tilde\sigma(i)$ if $i&lt;i_0$ and $\tilde\sigma'(i)=\tilde\sigma(i-1)$ if $i&gt;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&lt;_{\tilde\sigma'}b$ iff $a&lt;_{\sigma'}b$.

Let $a,b \in l$.


If $a,b\in l_k$, $a&lt;_{\tilde\sigma} b$ iff $a&lt;_{\tilde\sigma'}b$ iff $a&lt;_{\sigma'}b$ iff $a&lt;_{\sigma}$.
If $a\in l_k$ and $b\in l_{k'}$ with $k&lt;k'$, by (A), $a&lt;_{i_0} b$ and we therefore have $a&lt;_{\sigma}b$. Since $l$ is sorted with respect to $&lt;_{\tilde\sigma}$, $a&lt;_{\tilde\sigma}b$. So we indeed have $a&lt;_{\tilde\sigma}b$ iff $a&lt;_{\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 $&lt;_k$. Then, to test a candidate $i_0$, you only check that $L[J[i_0]\dots |L|]$ is sorted with respect to $&lt;_{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 $&lt;_{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).