Jonathan. Frech’s WebBlog

Sorting w. r. t. a partial ordering (#263)

Jonathan Frech,

Task. Given a type $T$$T$$T$, a fi­nite array $v=(n,\varphi)$$v=(n,\varphi)$$v=(n,\varphi)$ with $n\in\mathbb{N}_0$$n\in\mathbb{N}_0$$n\in\mathbb{N}_0$ and $\varphi:\{1..n\}\to T$$\varphi:\{1..n\}\to T$$\varphi:\{1..n\}\to T$ to­geth­er with a fi­nite set of pairs $K\subset T^2$$K\subset T^2$$K\subset T^2$, com­pute a permutation $\pi\in\mathbb{S}_n$$\pi\in\mathbb{S}_n$$\pi\in\mathbb{S}_n$ such that $v':=(n,\varphi\circ\pi)$$v':=(n,\varphi\circ\pi)$$v':=(n,\varphi\circ\pi)$ respects the strict partial ordering induced by $K$$K$$K$, pro­vid­ed $K$$K$$K$ is loop-free.
Fur­ther­more choose $\pi$$\pi$$\pi$ to respect relative ordering of equal elements, that is

$$\forall\,i<j\in\{1..n\}:\Big(v_i=v_j\implies\pi(i)<\pi(j)\Big).$$$$\forall\,i<j\in\{1..n\}:\Big(v_i=v_j\implies\pi(i)<\pi(j)\Big).$$$$\forall\,i<j\in\{1..n\}:\Big(v_i=v_j\implies\pi(i)<\pi(j)\Big).$$

An ap­pli­ca­tion of late is com­put­ing the ex­e­cu­tion order of inter-de­pen­dent transformers.

Pos­si­bly due to the seeming banality of the ap­pli­ca­tion, my many first presumptuous attempts were both of questionable algorithmic complexity as well as failing in subtle ways, fostering bugs which on­ly seldom showed their ugly faces. Fed up with hotfixed bypasses and manual pre-ordering, I badly longed after an im­ple­men­ta­tion which indeed took some time to get right:

Heart of my ap­proach I will herein pre­sent is com­put­ing a to­tal ordering on all order-participating values $L:=\bigcup\{\{x,y\};(x,y)\in K\}$$L:=\bigcup\{\{x,y\};(x,y)\in K\}$$L:=\bigcup\{\{x,y\};(x,y)\in K\}$ that is compatible with $K$$K$$K$ and thus an apt choice for a sorting key to attain $\pi$$\pi$$\pi$ by arbitrary extension to $v$$v$$v$.
For this consider the digraph $D:=(L,K)$$D:=(L,K)$$D:=(L,K)$ and inductively deconstruct it to form a $K$$K$$K$-conforming array $(\#L,\varphi_L:\{1..\#L\}\to L)$$(\#L,\varphi_L:\{1..\#L\}\to L)$$(\#L,\varphi_L:\{1..\#L\}\to L)$. Care must be taken, how­ev­er, to correctly position elements left of a node of min­i­mal degree three as e. g. greedily seeking chains may disregard local element relations. As such, iteratively pluck an ar­bi­trari­ly cho­sen min­i­mal element, laying these out from left to right via $\varphi_L$$\varphi_L$$\varphi_L$. Their minimality ensures that no element can contradict $K$$K$$K$ going down.
When using a stable sorting algorithm which sorts under $\varphi_L$$\varphi_L$$\varphi_L$, relative ordering is naturally respected as desired.

I wrote a quadratic im­ple­men­ta­tion in Haskell that on­ly stipulates Eq a: sort-via.hs. To achieve the complexity typically sought after for sorting tasks, I suspect an underlying to­tal order on the elements is required for data man­age­ment. Avoiding Haskell’s non-ADT containers and disappointing stan­dard li­brary support for ran­dom num­ber generation, I wrote a C++ im­ple­men­ta­tion and test suite test­ing both: sort-via.cpp, Makefile.