This surely has been done, maybe I googled the wrong adjective...
Define a raggedness measure $r$ of a sequence $S$ in this way:
- Two members $S_i,S_j$ of the sequence (who don't have to be adjacent!) are called neighbors if $\not\exists_{k\in]i,j[}|S_k\in]S_i,S_j[$.
- Example: $S=(1,4,3,2,5)$. 4 and 5 are neighbors (3 and 2 are outside of their size interval), 4 and 2 are not (3 falls inbetween), 1 and 4 are, 4 and 3 are (up or down doesn't matter).
- $r=card(neighbor-pairs(S))/n$ ($r=8/5$ for the example)
- WLOG for $S$ we can limit ourselves to permutations of $\{1,\dots,n\}$. (Some series below are noninteger, we can simply "stretch" them to integer.)
$r$ is at minimum $O(1)$ (obvious, all adjacent members of $S$ are also neighbors) and at maximum $O(\log n)$ (this follows from a seminal result of E.Demaine on binary search trees). Some further examples that I tried:
- $S=id, r=1$ (trivial)
- $S$ is the bitwise permutation, $r=O(\log n)$ (well known)
- $S$ is the Gray code permutation, $r=185/48$ if I could compute and sequence-guess correctly :-)
- $S$ is the Farey series sorted by denominator and then by nominator, $r=O(\log n)$ (says the experiment - can you verify?)
- $S$ is the Stern-Bacrot series, my best guess is $r=O(\log n)$ again (ditto?)
My questions:
- Do you have a reference for sequence raggedness in general?
- Do you have a reference for this measure in particular?
- Do you have an idea for some (not too convoluted :-) $S$ with $O(1)<r<O(\log n)$?
