0
$\begingroup$

Is there a straightforward way to characterise the number of inversions in an array of length N having distinct elements, each element an integer from 1 to N?

It's for a constraint optimization problem, where the number of inversions needs to be minimized.

$\endgroup$
1
  • $\begingroup$ In order to avoid the XY problem, it should be helpful to explain that constraint optimization problem. Or, at least, provide an accessible reference to the problem. $\endgroup$
    – John L.
    Apr 26, 2019 at 16:12

1 Answer 1

Reset to default
2
$\begingroup$

You can count inversions efficiently by adapting mergesort, but the most intuitive way is to just count all pairs:

$$\text{inv}(A) = \sum_{i=1}^{|A|}\sum_{j=i+1}^{|A|}[A_j<A_i]$$

Where $[A_j < A_i] = 1$ when $A_j < A_i$ and $0$ otherwise.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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