aakarshmadhavan's blog

Count number of arrays with k-inversions
By aakarshmadhavan, history, 8 years ago, In English

I'm trying to come up with a recursive solution for this problem but I haven't been able to so far. Any advice/pointers here?

I tried 0-1 knapsack style but there is an issue with backtracking the array.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It appears that the statement is actually asking for the number of permutations of 1... n with k inversions. If In(t) is the number of permutations of size n with t inversions, then . This recurrence can be calculated in O(nt) using prefix sums on In.

→ Reply