7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – D.W. May 9 at 2:06
  • $\begingroup$ @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! $\endgroup$ – Display Name May 9 at 13:44
  • $\begingroup$ @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. $\endgroup$ – xavierm02 May 9 at 18:44
  • $\begingroup$ @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. $\endgroup$ – Display Name May 9 at 19:00
4
$\begingroup$

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<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<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<i_0$ 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<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).

$\endgroup$
  • 2
    $\begingroup$ 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}$? $\endgroup$ – D.W. May 9 at 16:07
  • $\begingroup$ @D.W. I added stuff $\endgroup$ – xavierm02 May 9 at 18:21
  • $\begingroup$ 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. $\endgroup$ – Mees de Vries May 10 at 10:48
  • $\begingroup$ @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. $\endgroup$ – xavierm02 May 10 at 11:00
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ @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). $\endgroup$ – xavierm02 May 11 at 18:52
  • $\begingroup$ @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). $\endgroup$ – xavierm02 May 11 at 18:53
  • $\begingroup$ (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. $\endgroup$ – Emil Jeřábek supports Monica May 11 at 19:46

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.