patternMinor
Faster algorithm for a specific inversion
Viewed 0 times
fasteralgorithmforspecificinversion
Problem
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.
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.
Solution
Each element $j$ contributes $1$ to the cardinality of all sets $\{j > i \mid \sigma_j > i\}$ for which $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$.
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$.
Context
StackExchange Computer Science Q#142180, answer score: 7
Revisions (0)
No revisions yet.