How to implement inversion count in q?

Community Support
1

I’m trying to solve inversions count problem in q.
I think merge sort is not  suitable here and I implemented this in O(n*n) way.

Here is the code,

inversion1:{[x] y:(1+til count x)#\:x; sum sum each y >' x}inversion2:{[x] len:count x;cnt:0; i:0; while [i<len;j:i+1;while[j<len;if[x[i]>x[j];cnt+:1];j+:1];i+:1]; cnt}

Then I tested these 2 functions with \ts command.

a:100?100\ts inversion1 a\ts inversion2 a

In inversion1, I used adverb, so the speed was fast but consumed  plenty of space (a lot of temp sublist generated).

In inversion2, there’s no adverb, it’s only a violent in-place implementation, so space consumption was fine but when the size of list > 10000, the speed was unacceptable.

Is there any elegant way to solve inversion count  problem or any suggestions to my code so I can get time and space acceptable? 

Thanks.

2

inversion1 can be simplified as {sum(,/)x>'(1_)[1_x]}, though I don’t think it will use less memory than the original version. Is temp memory usage an issue with your system?

3

Something like this should be better on memory as you aren’t creating bit temp variables

q)\ts r2:{sum {sum y > z _ x}'[x;1+til count x]}a                                                                                                                 

355 422752

There might be better ways

4

Right, this alternative looks good. And it can be further simplified as {sum{sum x[y]>(1+y)_x}/:[x;til count x]}

5

Thanks, it’s awesome.