**Xi'an's Og » R**, and kindly contributed to R-bloggers)

**T**he puzzle of last weekend in ** Le Monde** was about finding the absolute rank of x

_{9}when given the relative ranks of x

_{1},….,x

_{8}and the possibility to ask for relative ranks of three numbers at a time. In R terms, this means being able to use

> rank(x[-9]) [1] 1 7 4 6 8 3 2 5 > rank(x[1:3]) [1] 1 3 2

or yet being able to sort the first 8 components of x

> x[-9]=sort(x[-9]) > rank(x) [1] 1 3 2

and then use rank() over triplets to position x_{9} in the list. If x_{9} is an extreme value, calling for its rank relative to x_{1} and x_{8} is sufficient to find its position. Else repeating with the rank relative to x_{2} and x_{7}, then relative to x_{3} and x_{6} , etc., produces the absolute rank of x_{9} in at most 4 steps. However, if we first get the rank relative to x_{1} and x_{8}, then the rank relative to x_{4} and x_{5}, we only need at most an extra step to find the absolute rank of x_{9} in thus at most 3 steps. Yet however, if we start with the rank relative to x_{3} and x_{6}, we are left with a single rank call to determine the absolute rank of x_{9} since, whatever the position of x_{9} relative to x_{3} and x_{6}, there are only two remaining numbers to compare x_{9 }with. So we can find the absolute rank of x_{9} in exactly two calls to rank.

**T**he second part of the puzzle is to determine for an unknown series x of 80 numbers the maximum number of calls to rank(c(x_{1},x_{2},x_{3})) to obtain rank(x). Of course, the dumb solution is to check all 82160 triplets, but I presume a sort of bubble sort would do better, even though Wikipedia tells me that bubble sort has worst-case and average complexity both *О*(*n*^{2}), while quicksort has an average (if not worse-case) *O*(*n*log*n*) complexity…. If we follow the one-step procedure obtained in the first part, starting with three numbers whose relative rank is obtained with one call, we need *in toto*

1 + (9-3)*2 + ((1+3*8+2)-9)*3+(80-27)*4 =279

calls to rank since 80<1+3*(3*8+2)+2=81.

Filed under: R Tagged: mathematical puzzle, R, rank

**leave a comment**for the author, please follow the link and comment on his blog:

**Xi'an's Og » R**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...