5

我有一个正分数列表：

[98.5, 85, 50, 50, 23, 0, 0, 0]

我想为这些分数分配排名：

[1, 2, 3, 3, 4, 5, 5, 5]

当两个连续的分数具有相同的值时，它们获得相同的排名。知道如何以实用的方式解决这个问题吗？

（发布在 Haskell 和 Ruby 中，因为我认为这两种解决方案都是可行的并且可以移植）

4

6 回答 6

12

在红宝石中：

a = [98.5, 85, 50, 50, 23, 0, 0, 0]
sorted = a.sort.uniq.reverse
a.map{|e| sorted.index(e) + 1}
# => [1, 2, 3, 3, 4, 5, 5, 5]
于 2013-10-07T20:59:26.977 回答
7

哈斯克尔：

{-# LANGUAGE TupleSections #-}
import Data.List
import Data.Maybe (mapMaybe)
import Data.Function (on)

rank, rank' :: [Double] -> [Int]

rank ls = mapMaybe (fmap (+1) . (`elemIndex` sorted)) ls
  where sorted = reverse . nub $ sort ls

-- Or Fixnum's faster solution
rank' = map fst . sortBy (compare `on` snd)
      . concat . zipWith (\n -> map (n,)) [1..]
      . groupBy ((==) `on` snd)
      . sortBy (flip compare `on` snd) . zip [1::Int ..]

有趣的是，rank这几乎是sawa的答案。nub<=>uniq和elemIndex<=> index。

于 2013-10-07T20:59:19.827 回答
2

我们是否假设分数已经排序？

如果不能假定它们已排序，请按照以下方法解决它：

Prelude Data.List Data.Function> let f = (const .) . (,) :: a -> b -> c -> (a,b)
Prelude Data.List Data.Function> let sor s = sortBy ((flip compare) `on` snd) s
Prelude Data.List Data.Function> let rank scores = map fst . sor . concat . 
        zipWith (map . uncurry . f) [1..] . groupBy ((==) `on` snd) . 
        sor . zip [1,0..] $ scores
Prelude Data.List Data.Function> rank [11,13,13,12]
[3,1,1,2]

首先，为每个分数附加一个反向索引。然后按元组的第二个投影降序排序。按第二个投影分组为我们提供了必须具有相同排名的分数列表列表。使用排名列表进行压缩会将排名 1 分配给最大的数字。通过使用函数f，我们同时丢弃了实际分数，使元组成为一对（排名，反向索引）。现在需要按照反向索引的降序对这些元组进行排序，得到第一个投影——排名。

于 2013-10-08T15:58:22.017 回答
2 
a = [98.5, 85, 50, 50, 23, 0, 0, 0]


a.uniq.
  sort_by(&:-@).
  each_with_index.
  with_object({}) { |(x,i),h| h[x] = i+1 }.
  values_at(*a)

最苛刻的操作是Enumerable#sort_by所以这个计算的计算复杂度为 O(n log(n)) 其中n = a.size. 相比之下，@sawa 的答案的计算复杂度为 O(n n)。我不知道 Haskell，所以无法评论这些答案的计算复杂性。

另请参阅Numeric#-@和Hash#values_at。

于 2013-10-07T21:31:30.743 回答
1

如果它们已经排序， 递归

eqNext (x:xs@(y:_)) acc = 
    let acc1 = if x == y then acc else acc + 1 in 
    acc1 : eqNext xs acc1
eqNext _ _ = []

els = 1 : eqNext ls 1

让我们检查：

> let ls = [98.5, 85, 50, 50, 23, 0, 0, 0]
> els
[1,2,3,3,4,5,5,5]

相同的非递归：

els = snd $ mapAccumL accF (0,0) ls
     where
      accF(ac,prev) b = let a1 = if ac == 0 || b /= prev then ac + 1 else ac in 
        ((a1,b), a1)
于 2013-10-07T21:48:29.843 回答
1

另一个红宝石答案:)

data = [98.5, 85, 50, 50, 23, 0, 0, 0, 85]
data.map{|value| data.select{|item| item > value }.size + 1 }

=> [1, 2, 4, 4, 6, 7, 7, 7, 2]

于 2015-08-17T08:18:28.133 回答