0
$\begingroup$

We are given two numbers N and K.

N <= 10^9.

K<=min{1000,(N*(N-1))/2}

We need to find numbers of permutations of ( 1 to N ) such that inversions are exactly K.

If N was <= 10^3. It would be a simple Dynamic programming question.

https://www.geeksforgeeks.org/number-of-permutation-with-k-inversions/

can we optimize it?

$\endgroup$
4
$\begingroup$

This is only a sketch of solution (there might be some off-by-ones)


Looking at a permutation of $\{1\ldots,n\}$ is equivalent at looking its inversion table $(a_1, \ldots, a_n)$ where $a_i$ is the number of elements to the left of $i$ that are greater than $i$. Basically that gives you a bijection between $S_n$ and $\prod_{1\le i\le n} \{0,\ldots,i-1\}$ and the number of inversions of the permutation is exactly the sum of all $a_i$ corresponding to it (see for example Knuth TAOCP volume 3 for a nice development).

So the problem is equivalent to computing the cardinal of:

$$\{(a_1, \ldots, a_n) \in \prod_{i=1}^{n}\{0,\ldots,i-1\}, \sum_{i=1}^n a_i=k\}$$

This way, we find a DP algorithm with $n\times k$ states:

$$\text{dp}(n,k)=\sum_{i=0}^{\min(k,n-1)}\text{dp}(n-1,k-i)$$

Thus:

  • When $n$ is small ($n\le k+1$):

$$\text{dp}(n,k)=\sum_{i=0}^{n-1}\text{dp}(n-1,k-i)=\text{dp}(n,k-1)+\text{dp}(n-1,k)$$

So you can compute these in $O(k^2)$. In particular, we will need the following vector of size $k$:

$$\begin{bmatrix} \text{dp}(k+1,0)\\ \vdots\\ \text{dp}(k+1,k) \end{bmatrix}$$

  • When $n$ is large ($n>k+1$):

$$\text{dp}(n,k)=\sum_{i=0}^{k}\text{dp}(n-1,k-i)=\sum_{i=0}^k \text{dp}(n-1,i)$$

In this case $\text{dp}(n,\cdot)$ depends linearly on $\text{dp}(n-1,\cdot)$, the matrix being a $k\times k$ lower triangular matrix with nonzero coefficients being all 1-s. More formally, you can rewrite the previous equality as:

$$\begin{bmatrix} \text{dp}(n,0)\\ \vdots\\ \text{dp}(n,k) \end{bmatrix}= \begin{bmatrix} 1&0&\ldots&\ldots&0\\ 1&1&0&\ldots&0\\ \vdots&\vdots&\ddots&\ddots&\vdots\\ 1&1&\ldots&1&0\\ 1&1&\ldots&1&1 \end{bmatrix} \begin{bmatrix} \text{dp}(n-1,0)\\ \vdots\\ \text{dp}(n-1,k) \end{bmatrix}$$

Just let me note:

$$A=\begin{bmatrix} 1&0&\ldots&\ldots&0\\ 1&1&0&\ldots&0\\ \vdots&\vdots&\ddots&\ddots&\vdots\\ 1&1&\ldots&1&0\\ 1&1&\ldots&1&1 \end{bmatrix}$$

Now if you iterate the relation, you will get for any $i$:

$$\begin{bmatrix} \text{dp}(n+i,0)\\ \vdots\\ \text{dp}(n+i,k) \end{bmatrix}= A^i \begin{bmatrix} \text{dp}(n,0)\\ \vdots\\ \text{dp}(n,k) \end{bmatrix}$$

In particular:

$$\begin{bmatrix} \text{dp}(n,0)\\ \vdots\\ \text{dp}(n,k) \end{bmatrix}= A^{n-k-1} \begin{bmatrix} \text{dp}(k+1,0)\\ \vdots\\ \text{dp}(k+1,k) \end{bmatrix}$$

The vector on the left hand side is what we want ($\text{dp}(n,k)$), the vector on the right hand side is what we computed in the first step (when $n$ is small). So if we can compute the $k\times k$ matrix $A^{n-k-1}$, computing the answer can be done in $O(k^2)$.


Now let's see how fast we can compute $A^{n-k-1}$. I suggest three different ideas (I assume that you want the answer modulo some prime $p$):

1) Matrix exponentiation: if we can multiply $k\times k$ matrices with coefficients in $\mathbb{Z}_p$ in time $O(k^\omega)$), you can use fast exponentiation to have a $O(k^\omega \log n)$ algorithm ($\omega =2.38$ nowadays). Actually, if you are fine with a $O(k^3 \log n)$ algorithm, this should be easy to code (with the naive matrix multiplication algorithm)

2) Polynomial interpolation: if you look at the coefficients of $(A^T)^n$, it looks like:

$$(A^T)^n=\begin{bmatrix} P_1(n)&P_2(n)&\ldots&P_k(n)\\ 0&P_!(n)&\ldots&P_{k-1}(n)\\ \vdots&\ddots&\ddots&\vdots\\ 0&\ldots&0&P_1(n) \end{bmatrix}$$

where $P_1, \ldots, P_k$ are polynomials with integer coefficients and $P_i$ is of degre $i-1$. They satisfy some kind of "generalized Pascal triangle relationship":

$$P_i(n)=1+\sum_{j=0}^{n-1}P_{i-1}(j)$$

So it's possible to compute $P_i(j)$ for $1\le i \le k$ and $0\le j\le k-1$ in $O(k^2)$. We can find coefficients of $P_i$ by doing a Newton interpolation in $O(k \log k)$, so this should give a $O(k^2 \log k)$ algorithm.

3) Find a closed form for $A^i$ with the help of some well-known combinatorial objects. As I said in the comments, the polynomials $P_1, \ldots, P_k$ are close to Faulhaber's polynomials which can be computed in linear time. This might require some heavy handmade computation. I think it should lead to a $O(k^2)$ algorithm.

$\endgroup$
  • $\begingroup$ I did not understand from "the matrix being a k×k ...". Could you please give me a little example? $\endgroup$ – Learner007 Oct 6 at 21:40
  • $\begingroup$ @Learner007 You're right to be suspicious, because it's wrong indeed: it's a lower triangular matrix consisting only of 1 (if you write the vector $x_n=(\text{dp}(n,0),\ldots,\text{dp}(n,k))$, you have $x_n=A x_{n-1}$). So my answer is actually not very satisfying as such: you'll have a $O(k^3\log n)$ algorithm (or $O(k^{2.37}\log n)$ if that's a theoretical question), I need to sleep right now but meanwhile you can investigate what powers of this matrix $A$ are like (you'll get $k$ interesting polynomials in $n$ of degree $\le k$, not sure whether they are easy to compute) $\endgroup$ – md5 Oct 6 at 23:27
  • $\begingroup$ My conjecture would be that the coefficients of these polynomials are computable in $O(k^2)$, because they are very similar to the Faulhaber's polynomials (en.wikipedia.org/wiki/Faulhaber%27s_formula), which only involve Bernoulli's numbers $\endgroup$ – md5 Oct 6 at 23:41
  • $\begingroup$ if I want to use this method N=6 and K=3 can you explain using this example? $\endgroup$ – Learner007 Oct 7 at 10:45
  • $\begingroup$ @Learner007: I tried to be a little bit more precise (also I added description of a $O(k^2 \log k)$ algorithm). Tell me if that's still unclear (tbh matrices in LaTeX are a bit of a pain to write) $\endgroup$ – md5 Oct 7 at 12:33
1
$\begingroup$

You could look at the answers to this question on SO: https://stackoverflow.com/questions/19372991/number-of-n-element-permutations-with-exactly-k-inversions (in particular the part about Mahonian numbers)

Additionally, it seems that dynamic programming with memoisation runs in $\mathcal{O}(N\cdot k)$ [NB: I didn't actually check this, it's in one of the answers to the linked question]: if this is for a competitive programming problem, you might consider trying it: even though in theory $N\cdot k$ can be as large as $10^{12}$, the judge system may test/query only reasonable cases (it happens).

$\endgroup$

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.