We first introduce some formalism of inversions. Let \(\tau =(v_1, \dots , v_n)\)  be an ordering of a set \(N\) . An inversion on position \(i \in [1, n-1]\) transforms \(\tau \)  into the ordering \(h_i(\tau ) := (v_1, \dots , v_{i-1},v_{i+1},v_i, \dots , v_n)\) . A sequence of inversions \(S=(s_1, \dots , s_\ell )\)  is a finite sequence of elements in \([1, n-1]\) . Applying \(S\)  on \(\tau \)  transforms \(\tau \)  into the ordering \(S(\tau ):=h_{s_\ell }\circ h_{s_{\ell -1}} \circ \dots \circ h_{s_1}(\tau )\) . The distance \(\operatorname{Inv}(\tau ,\tau ^{\prime })\)  is the length of the shortest sequence of inversions \(S\)  such that \(S(\tau )=\tau ^{\prime }\) . Recall that the inversions-distance is also known as the Kendall tau distance [1]}.
