# Faster algorithm for a specific inversion

There is a permutation (more precisely a derangement) $$\sigma$$ of the set $$\{0,1,\dots,n-1\}$$ with cardinality $$n$$.

I want to compute the following counts (a kind of inversion):

$$K(\sigma )_{i}=\#\{j>i:\sigma _{j}>i\}$$

for each $$0 \le i \lt n$$.

Obviously a $$O(n^2)$$ straight-forward algorithm computes these counts. But can it be done faster (eg in $$O(n \log n)$$)?

I can't seem to wrap my head around such an algorithm, based on other divide-and-conquer algorihms for usual inversions, at least so far.

Background: The counts above are used in a custom algorithm to rank and unrank derangements in lexicographic order and their computation is the main bottleneck of the algorithm.

• Visualising the problem helps here. You have got a permutation matrix, represented by recording for each row the column where it has a nonzero entry. In $O(n)$ time, you can get the "transposed" information (corresponding to $\sigma^{-1}$) as well, if you should need it, The problem is to count, for each $i$, the sum of entries in the bottom-right square $(n-i)\times(n-i)$ matrix; by looking at the differences for adjacent $i$, this can be done in a single pass. Commented Jul 11, 2021 at 11:39

Each element $$j$$ contributes $$1$$ to the cardinality of all sets $$\{j > i \mid \sigma_j > i\}$$ for which $$i < \min\{\sigma_j, j\}$$, and $$0$$ to the other sets.

You can compute all $$n$$ values $$K(\sigma)_i$$ in $$O(n)$$ time as follows. Maintain an array $$A[0, \dots, n-1]$$ where each entry $$A[i]$$ is initialized to $$0$$. Then, for each $$j$$, increment $$A[\min\{\sigma_j, j\}]$$ by $$1$$.

Compute the sums of the elements in all suffixes of $$A$$, i.e., construct a new array $$K[1, \dots, n-1]$$ such $$K[i] = \sum_{i' > i} A[i']$$. This can be done in $$O(n)$$ time by setting $$K[n-1]=0$$ and, for all $$i=n-2, \dots, 0$$ (in this order), $$K[i] = K[i+1] + A[i+1]$$.

Clearly, the above can also be done in-place without the need of the additional array $$K$$.

• Excellent! Can a similar strategy be applied to count $K'(\sigma )_{i}=\#\{j<i:\sigma _{j}>i\}$?? Commented Jul 10, 2021 at 14:56
• $$|\{ j < i : \sigma_j > i \}| + |\{ j > i : \sigma_j > i \}| + |\{ i : \sigma_i > i \}| = |\{ j \mid \sigma_j > i \}.|$$ Substituting: $$K'(\sigma)_i + K(\sigma)_i + 1_{\sigma_i > i} = n-i-1.$$ Therefore: $$K'(\sigma)_i = n-i-1 - K(\sigma)_i - 1_{\sigma_i > i}$$ Commented Jul 10, 2021 at 15:02
• hmm, $K'(\sigma)$ is needed in unranking, and we dont have $K(\sigma)$ as we dont have yet the permutation, it is built step-by-step Commented Jul 10, 2021 at 15:04
• Uhm... $K'(\sigma)_i$ is defined as a function of sigma. How would you compute $K'(\sigma)_i$ in the first place (even in a non-efficient way) if you don't know $\sigma$? Commented Jul 10, 2021 at 15:06
• $K'(\sigma)$ is based strictly on previous entries Commented Jul 10, 2021 at 15:07