3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Jul 11, 2021 at 11:39

1 Answer 1

7
$\begingroup$

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

$\endgroup$
14
  • $\begingroup$ Excellent! Can a similar strategy be applied to count $K'(\sigma )_{i}=\#\{j<i:\sigma _{j}>i\}$?? $\endgroup$
    – Nikos M.
    Commented Jul 10, 2021 at 14:56
  • 1
    $\begingroup$ $$|\{ 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} $$ $\endgroup$
    – Steven
    Commented Jul 10, 2021 at 15:02
  • $\begingroup$ 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 $\endgroup$
    – Nikos M.
    Commented Jul 10, 2021 at 15:04
  • $\begingroup$ 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$? $\endgroup$
    – Steven
    Commented Jul 10, 2021 at 15:06
  • $\begingroup$ $K'(\sigma)$ is based strictly on previous entries $\endgroup$
    – Nikos M.
    Commented Jul 10, 2021 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.