23
\$\begingroup\$

Task

Given an input list of integers x1…xn, compute a list of ranks r1…rn (a permutation of {1…n}) so that xr1 ≤ xr2 ≤ … ≤ xrn. Then, for each xi, replace its rank by the arithmetic mean of the ranks of all values in x that are equal to xi. (That is, whenever there is a tie between equal values in x, fairly redistribute the ranks among all of them.) Output the modified list of ranks r’1…r’n.

(For statistics geeks: such a ranking of observations is used in the Mann–Whitney U test (method two, step 1.))

Example

Given an input list [3, -6, 3, 3, 14, 3], the first list of ranks would be [2, 1, 3, 4, 6, 5], which would sort the list into [-6, 3, 3, 3, 3, 14]. Then, the ranks for all 3s in the input list are evened out into (2 + 3 + 4 + 5) ÷ 4 = 3.5. The final output is [3.5, 1, 3.5, 3.5, 6, 3.5].

Test cases

[4, 1, 4] -> [2.5, 1.0, 2.5]
[5, 14, 14, 14, 14, 5, 14] -> [1.5, 5.0, 5.0, 5.0, 5.0, 1.5, 5.0]
[9, 9, -5, -5, 13, -5, 13, 9, 9, 13] -> [5.5, 5.5, 2.0, 2.0, 9.0, 2.0, 9.0, 5.5, 5.5, 9.0]
[13, 16, 2, -5, -5, -5, 13, 16, -5, -5] -> [7.5, 9.5, 6.0, 3.0, 3.0, 3.0, 7.5, 9.5, 3.0, 3.0]

Rules

This is , so the shortest code in bytes wins.

\$\endgroup\$

11 Answers 11

7
\$\begingroup\$

Jelly, 10 8 bytes

ð_'Ṡ‘S‘H

Saved 2 bytes by using the cmp trick from @xnor's answer.

Try it online! or verify all test cases.

How it works

ð_'Ṡ‘S‘H  Main link. Left argument: A (list of values)

ð         Make the chain dyadic, setting the right argument to A.
 _'       Spawned subtraction; compute the matrix of differences.
   Ṡ      Apply the sign function to each difference.
    ‘     Increment.
     S    Sum across columns.
      ‘   Increment.
       H  Halve.
\$\endgroup\$
6
\$\begingroup\$

Pyth, 12

m+l<#dQ.OS/Q

Test Suite

For each value this computes the arithmetic mean of [1..frequency] and adds the count of values less than the current one.

This works because for each value we would compute:

(1 / frequency) * sum (i = 1..frequency) i + count_less

which we can simplify to:

(1 / frequency) * [ frequency * (frequency + 1) / 2 + count_less * frequency ]

and again to:

(frequency + 1) / 2 + count_less

However, in Pyth it was golfier to compute the first summand by using the mean builtin, rather than this other formula.

\$\endgroup\$
4
\$\begingroup\$

Python 2, 51 bytes

lambda l:[-~sum(1+cmp(y,x)for x in l)/2.for y in l]

For each element y, the cmp expression gives 2 points for each smaller x and 1 point for each equal x. This sum is rescaled into the right range by adding 1 and halving. The 2. is needed to avoid integer division.

Python 3, 52 bytes

Python 3 lacks cmp, requiring a Boolean expression (+2 bytes), but it has float division (-1 byte).

lambda l:[-~sum((y>x)+(y>=x)for x in l)/2for y in l]
\$\endgroup\$
3
\$\begingroup\$

MATL, 14 bytes

7#utG&S&S2XQw)

Try it online! Or verify all test cases (slightly modified version of the code; each result is on a different line).

      % Implicit input. Example: [5 14 14 14 14 5 14]
7#u   % Replace each value by a unique, integer label. Example: [1; 2; 2; 2; 2; 1; 2]
t     % Duplicate
G&S   % Push input again. Sort and get indices of the sorting. Example: [1 6 2 3 4 5 7]
&S    % Sort and get the indices, again. This gives the ranks. Example: [1 3 4 5 6 2 7]
2XQ   % Compute mean of ranks for equal values of the integer label. Example: [1.5; 5]
w     % Swap top two elements in stack
)     % Index the means with the integer labels. Example: [1.5; 5; 5; 5; 5; 1.5; 5]
      % Implicit display
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 13 bytes

Code:

v¹y‹O¹yQO>;+ˆ

Uses the CP-1252 encoding. Try it online!.

\$\endgroup\$
3
\$\begingroup\$

R, 17 12 bytes

Takes the input from STDIN outputs to STDOUT. If the output is flexible then we can ditch the cat().

rank(scan())

Fairly simple, uses the builtin rank that defaults to average for a tie breaker.

In use:

> rank(scan())
1: 5 14 14 14 14 5 14
8: 
Read 7 items
[1] 1.5 5.0 5.0 5.0 5.0 1.5 5.0
> rank(scan())
1: 3 -6 3 3 14 3
7: 
Read 6 items
[1] 3.5 1.0 3.5 3.5 6.0 3.5
> 
\$\endgroup\$
  • \$\begingroup\$ You may drop the cat(), if it’s up to me. I don’t know what the community consensus is, though. \$\endgroup\$ – Lynn Jun 1 '16 at 19:06
  • \$\begingroup\$ @Lynn Thanks I will. I can always put it back. \$\endgroup\$ – MickyT Jun 1 '16 at 19:11
2
\$\begingroup\$

J, 18 bytes

1-:@+1+/"1@:+*@-/~

Based on Dennis' solution using xnor's method.

Using a straight-forward approach requires 24 bytes for me.

(i.~~.){](+/%#)/.1+/:@/:

Usage

   f =: 1-:@+1+/"1@:+*@-/~
   f 3 _6 3 3 14 3
3.5 1 3.5 3.5 6 3.5
   f 4 1 4
2.5 1 2.5
   f 5 14 14 14 14 5 14
1.5 5 5 5 5 1.5 5
   f 9 9 _5 _5 13 _5 13 9 9 13
5.5 5.5 2 2 9 2 9 5.5 5.5 9
   f 13 16 2 _5 _5 _5 13 16 _5 _5
7.5 9.5 6 3 3 3 7.5 9.5 3 3
\$\endgroup\$
1
\$\begingroup\$

Actually, 18 bytes

;╗`╝╜"╛-su"£MΣu½`M

Try it online!

This is essentially a port of xnor's Python solution.

Explanation:

;╗`╝╜"╛-su"£MΣu½`M
;╗                  push a copy of input to reg0
  `             `M  for x in input:
   ╝                  push x to reg1
    ╜                 push input from reg0
     "    "£M         for y in input:
      ╛                 push x from reg0
       -s               cmp(y,x) (sgn(y-x))
         u              add 1
             Σu½      sum, add 1, half
\$\endgroup\$
1
\$\begingroup\$

APL, 17 chars

(y+.×⍋X)÷+/y←∘.=⍨X

Assuming the list is stored in X.

Explanation:

Note that APL evaluates expressions from right to left. Then:

  • ∘.=⍨X = X∘.=X where ∘.= is the outer product using = as dyadic function. (Where you normally would multiply. So the mathematical outer product may be written as ∘.×.)
  • The resulting matrix is stored in y and y is directly folded using + to give a vector of the number of equal objects for each rank (lets call it z←+/y).
  • ⍋X returns the ranks of X
  • y+.×⍋X gives the inner product of our matrix y with this vector.
  • The result is divided (component wise) by z.
\$\endgroup\$
0
\$\begingroup\$

Julia, 30 bytes

!x=-~sum((x.>x')+(x.>=x'),2)/2

This uses an approach from @xnor's answer. Julia has cmp, but it doesn't vectorize.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 49 48 bytes

a=>a.map(n=>a.reduce((r,m)=>r+(n>m)+(n>=m),1)/2)

Edit: Saved 1 byte by reformulating the expression so it now looks like @xnor's Python 3 answer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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