Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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<g(s)<1$ for $s$ without order, but $g(s_1) > g(s_2)$ for $s_1$ less "decreased ordered" than $s_2$.

Any comments are appreciated.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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}.$$

share|improve this answer
    
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? –  Cameron Buie Oct 17 '12 at 23:07
    
yes, it looks like good formula for function $g$. –  ashim Oct 17 '12 at 23:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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