Return to Answer

• 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$ and such that for all $p\in P,L[p]\le_{\sigma}L[p+1]$, or Error if no such bijection exist.

• 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.

• 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 all $\sigma'$ that extends $\sigma$, $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$ and such that for all $p\in P,L[p]\le_{\sigma}L[p+1]$, or Error if no such bijection exist.

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

• Otherwise choose $p\in\{1,\dots,|L|-1\}$ such that either $p\not\in P$ or $f(p)<|I_\text{done}|$. If $p\in P$ and $f(p)<|I_\text{done}|$, let $i:=\sigma(f(p)+1)$, and otherwise set $P':=P\sqcup \{p\}$ and $i:=\sigma(1)$. Then:

  • If $L[p] <_i L[p+1]$ then recurse with $f'$ defined by $f'(p):=|I|$ and $f'(p'):=f(p')$ for all $p'\not=p$.
  • If $L[p] \sim_i L[p+1]$ then recurse with $f'$ defined by $f'(p):=f(p)+1$ and $f'(p'):=f(p')$ for all $p'\not=p$, and $J':=\{i\in J / L[p] \le_{i} L[p+1]\}$.
  • If $L[p] >_i L[p+1]$ then return Error.

• 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$ and such that for all $p\in P,L[p]\le_{\sigma}L[p+1]$, or Error if no such bijection exist.

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

• 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 all $\sigma'$ that extends $\sigma$, $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$ 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 $L[p]$ and $L[p+1]$ for each $P_\lt \sqcup P_\sim$ (and we use those two sets and $f$ to remember that result) 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$.

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

• Otherwise choose $p\in\{1,\dots,|L|-1\}$ such that either $p\not\in P$ or $f(p)<|I_\text{done}|$.

  • (A) If $p\in P$ and $f(p)<|I_\text{done}|$, let $i:=\sigma(f(p)+1)$.
    • If $L[p] <_i L[p+1]$ then recurse with $f'$ defined by $f'(p):=|I|$ and $f'(p'):=f(p')$ for all $p'\not=p$.
    • If $L[p] ~_i L[p+1]$ then recurse with $f'$ defined by $f'(p):=f(p)+1$ and $f'(p'):=f(p')$ for all $p'\not=p$, and $J':=\{i\in J / L[p] \le_{i} L[p+1]\}$.
    • If $L[p] >_i L[p+1]$ then return Error.
  • (B) If $p\not\in P$, set $P':=P\sqcup \{p\}$ and do (A) with $i:=\sigma(1)$.

• 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 all $\sigma'$ that extends $\sigma$, $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$ 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$.

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

• Otherwise choose $p\in\{1,\dots,|L|-1\}$ such that either $p\not\in P$ or $f(p)<|I_\text{done}|$. If $p\in P$ and $f(p)<|I_\text{done}|$, let $i:=\sigma(f(p)+1)$, and otherwise set $P':=P\sqcup \{p\}$ and $i:=\sigma(1)$. Then:

  • If $L[p] <_i L[p+1]$ then recurse with $f'$ defined by $f'(p):=|I|$ and $f'(p'):=f(p')$ for all $p'\not=p$.
  • If $L[p] \sim_i L[p+1]$ then recurse with $f'$ defined by $f'(p):=f(p)+1$ and $f'(p'):=f(p')$ for all $p'\not=p$, and $J':=\{i\in J / L[p] \le_{i} L[p+1]\}$.
  • If $L[p] >_i L[p+1]$ then return Error.