1
$\begingroup$

Following the issue from Faster algorithm for a specific inversion:

We have a permutation (a derangement actually) $\sigma$ of the set $\{0,1,\dots,n-1\}$ with cardinality $n$.

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

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

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

With the restriction that the computation should depend strictly on previously computed entries (as this is for unranking, the future entries of the permutation are not yet known).

For computing the complementary counts during ranking (the linked question), there is a linear algorithm rather than the straight-forward $O(n^2)$ algorithm.

Can a faster algorithm (than the straight-forward $O(n^2)$ computation) be applied also in this case (maybe linear or $O(n \log n)$)?

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$
2
$\begingroup$

Each $j$ contributes $1$ to all $K'(\sigma)_i$ with $j < i < \sigma_j$.

Ideally you want a data structure that maintains a collection of $n$ counters $C_0, \dots, C_{n-1}$ under the following operations:

  • Offset($j$, $\delta$): Given $j$ and $\delta$, add $\delta$ to each $C_i$ with $i \le j$.
  • Evaluate($i$): Return the value of $C_i$

When $\sigma_j$ is revealed, you can add $1$ to all $C_i$ with $j < i < \sigma_j$ (assuming the interval is non-empty) by performing the following two operations: (i) Offset($\sigma_j-1$, $1$), (ii) Offset($j$, $-1$). Then, you can recover the value of $K'(\sigma)_i$ by performing a Evaluate($i$) operation.

The rest of the answers describes how to implement a data structure supporting each of the above operations in $O(\log n)$ time, so that the overall time complexity will be $O(n \log n)$.

Suppose for simplicity that $n$ is a power of $2$, so that $k = \log n$. Instead of keeping a single set of counters $C_0, \dots, C_{n-1}$ (i.e., one for each $i$) keep multiple counters per element $i$.

The counters associated with $i$ will be $C^{(h)}_i$ for some suitably chosen values of $h$. In particular, if the binary expansion of $i$ has $\ell_i$ zeros in its least significant bit, then we will keep $\ell_i$ counters $C^{(0)}_i, C^{(1)}_i, \dots, C^{(\ell_i-1)}_i$. (If $\ell_i=0$, we keep no counters). The intuition is that adding $1$ to $C_i^{(h)}$ corresponds to adding $1$ to each of the $2^h$ "original counters" $C_i, C_{i+1}, \dots, C_{i+2^{h}-1}$. In particular we say that $C_i^{(h)}$ covers $C_i, C_{i+1}, \dots, C_{i+2^{h}-1}$.

See the figure for a graphical example with $n=16$.

example

To implement Offset($j$, $\delta$): write $j+1$ as a sum of (at most $\log n$) decreasing distinct powers of $2$ so that $j+1 = 2^{h_1} + 2^{h_2} + 2^{h_3} + \dots + 2^{h_m}$. Do the following:

  • Set $x = 0$.
  • For each $\ell = 1, \dots, m$:
    • Increment $C^{(h_\ell)}_x$ by $\delta$.
    • Increment $x$ by $2^{h_\ell}$.

For example when $j = 12$, we can write $j+1 = 13$ as $8 + 4 + 1 = 2^3 + 2^2 + 2^0$. To perform Offset($12$, $1$), we would add $1$ to $C_{0}^{(3)}$, $C_{8}^{(2)}$, $C_{12}^{(0)}$. These are exactly the counters corresponding to the intervals highlighted in red.

To recover the value of the "original counter" $C_i$, it suffices to sum the values of all counters $C_{i'}^{(h)}$ that cover $C_i$.

$\endgroup$
16
  • $\begingroup$ $O(n \log n)$ seems way better than $O(n^2)$, however I will implement the idea and get back to you. Thank you! $\endgroup$
    – Nikos M.
    Jul 10 '21 at 15:40
  • $\begingroup$ I cant seem to make it work correctly. I think the problem is in Offset(). Why is $j+1$ needed instead of $j$? The rest are straight-forward. $\endgroup$
    – Nikos M.
    Jul 10 '21 at 17:34
  • $\begingroup$ Note that $0 \le j \le n-1$, $0 \le \sigma_j \le n-1$, so $\sigma_j-1$ can become invalid value $\endgroup$
    – Nikos M.
    Jul 10 '21 at 17:41
  • $\begingroup$ I wrote down a quick implementation in C++, which appears to be working fine. Also, notice that I wrote that you need to perform the two offset operations only if the interval $j < i < \sigma_j$ is non-empty. $\endgroup$
    – Steven
    Jul 10 '21 at 22:31
  • $\begingroup$ The quantity $j+1$ represents the number of "original counters" we have to logically change when offset($j$, $\delta$) is called. $j+1$ (instead of $j$) is correct here since this is affecting the $j+1$ counters $C_0, C_1, \dots, C_{j}$. $\endgroup$
    – Steven
    Jul 10 '21 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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