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
    So to accomplish what the OP is trying to do, given a sequence $s$ of length $n>1$, we would define the function by $$g(s)=\frac{\text{Inv}(s)}{\binom n 2}=\frac{2\text{Inv}(s)}{n(n-1)},$$ yes?2012-10-17
  • 0
    yes, it looks like good formula for function $g$.2012-10-17