Блог пользователя flame_boy

Calculate number of permutations with ai<aj
Автор flame_boy, 11 месяцев назад, По-английски

Given an array of first n natural numbers. Calculate number of total permutations with exactly k pairs satisfy the condition a[i]<a[j] and i<j.

Example — n = 3, k = 2

All permutations — [1,2,3][1,3,2][2,1,3][2,3,1][3,2,1][3,1,2]

Output — 2 ([2,1,3][1,3,2])

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
11 месяцев назад, # |
← Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

Check this. The solution to your problem is $$$\frac{n(n - 1)}{2} - S$$$ where $$$S$$$ is the number of inversions.

→ Ответить
»
11 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

I don't know if there is a close formula, probably you can get something doing some algebra with generating functions, but since I haven't found anything I'll just explain a no brainer solution.

Notice that the generating function of the number of inversions is (1+$$$x$$$)(1+$$$x$$$+$$$x^2$$$)...(1+$$$x$$$+...+$$$x^{n-1}$$$).

Just use d&c NTT and output the $$$k$$$-th term in $$$O(n^2log^2n)$$$.

→ Ответить
  • »
    »
    11 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    For smaller $$$k$$$ you can actually solve it in $$$\mathcal{O}(k \log k)$$$. You need to find $$$\dfrac{(1-x)(1-x^2) \cdots (1-x^n)}{(1-x)^n}$$$. The numerator can be found by finding it's $$$ln$$$ (in $$$\mathcal{O}(k \log n)$$$, since $$$ln(1-x^n)$$$ has only $$$k/n$$$ non-zero coefficients before $$$k$$$) and finding it's exponent, then we'll only need to divide it by the denominator, so for $$$k > n$$$ it's $$$\mathcal{O}(k \log k)$$$. I doudt it can be done faster than $$$\mathcal{O}(k)$$$, so I think it's pretty close to optimal.

    → Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

maybe this will help(dp O(n^3)): https://cses.fi/problemset/result/8023530/

→ Ответить
»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Imagine a permutation of elements $$$1,2,\ldots,n-1$$$ with $$$k'$$$ desired pairs then inserting $$$n$$$ in the position $$$k-k'$$$. This will make it a permutation of $$$1,2,\ldots,n$$$ with exactly $$$k$$$ desired pairs. (only possible if $$$0 \leq k-k' \leq n$$$ or in other words, $$$k-n \leq k' \leq k$$$)

You can count with DP in $$$O(nk)$$$, which is technically $$$O(n^{3})$$$ since $$$k \leq n^{2}$$$.

Pseudocode:

fn dp(n, k) {
  if k <  0 { return 0 }
  if k == 0 { return 1 }
  ans = 0
  for k' = k-n ... k {
    ans += dp(n-1, k')
  }
  return ans
}
→ Ответить