1
$\begingroup$

Is there function $f(s)$ to measure "chaosity" of a sequence $s$? For example, sequence $s_1=1,2,3,4,5$ is ordered so $f(s_1)$ equals zero and $s_2 = 3,1,2,5,4$ is not actually ordered but less ordered than $s_3=1,2,3,5,4$, so $f(s_2) > f(s_3)$.

Is there function $g(s)$ to measure decreasing order, so $g(s) = 0$ for $s=1,2,3,4,5$, $g(s) = 1$ for $s=5,4,3,2,1$ and $0 for $s$ without order, but $g(s_1) > g(s_2)$ for $s_1$ less "decreased ordered" than $s_2$.

Any comments are appreciated.

1 Answers 1

1

The inversion number (that is, the number of pairs that are in the wrong order) is a measure of how far a sequence is from being sorted. The inversion number of a sorted sequence is zero, that of its reverse is $\binom n2$, and that of any other permutation lies between them.

I don't understand how your functions $f$ and $g$ are supposed to differ from each other, but you can certainly define the latter by scaling the inversion number to lie between zero and one: $g(s) = \frac{\operatorname{inv}(s)}{\binom n2}.$

  • 0
    yes, it looks like good formula for function $g$.2012-10-17