(*
ideone.com/gtRf08 をF#で実装しました。
nenono.hatenablog.com/entry/2015/05/08/111710 を参考にしました。
よりランキングっぽい出力を得るため、以下の仕様としました。
* 1 origin (最初の値は0位ではなく1位)
* 順位を決めるキーとなる値が等しいデータはすべて同一順位となる
* 1位→2位→2位 の次の値の順位は4位となる
*)
// F# 4.0なら以下の関数の代わりにSeq.indexedが使える
let indexed xs = xs |> Seq.mapi (fun i x -> i, x)
// F# 4.0なら以下の関数の代わりにSeq.mapFoldが使える
let mapFold mapping state xs =
let result = ((None, state), xs) ||> Seq.scan (fun (_, s) x -> let m, s = mapping s x in Some m, s)
(result |> Seq.map fst |> Seq.choose id), (result |> Seq.last |> snd)
// 関数の本体
let ranked rankProjection xs =
let rankMap =
let sorted = xs |> Seq.map rankProjection |> indexed |> Seq.sortBy snd |> indexed
((1, None), sorted) ||> mapFold (fun (r, b) (ai, (bi, k)) ->
let rank = if b = Some k then r else ai + 1
(bi, rank), (rank, Some k))
|> fst |> dict
xs |> List.mapi (fun i x -> rankMap.[i], x)
// テスト
let test() =
let inline shouldBe expected actual =
if expected <> actual then failwithf "expected %A, but %A" expected actual
let source = [
3, 2
1, 7
4, 1
1, 8
5, 2
9, 8
2, 1
]
let expected = [
4, (3, 2)
1, (1, 7)
5, (4, 1)
1, (1, 8)
6, (5, 2)
7, (9, 8)
3, (2, 1)
]
source |> ranked fst |> shouldBe expected
printfn "passed."
test()
KCoKaWRlb25lLmNvbS9ndFJmMDgg44KSRiPjgaflrp/oo4XjgZfjgb7jgZfjgZ/jgIIKbmVub25vLmhhdGVuYWJsb2cuY29tL2VudHJ5LzIwMTUvMDUvMDgvMTExNzEwIOOCkuWPguiAg+OBq+OBl+OBvuOBl+OBn+OAggoK44KI44KK44Op44Oz44Kt44Oz44Kw44Gj44G944GE5Ye65Yqb44KS5b6X44KL44Gf44KB44CB5Lul5LiL44Gu5LuV5qeY44Go44GX44G+44GX44Gf44CCCiogMSBvcmlnaW4gKOacgOWIneOBruWApOOBrzDkvY3jgafjga/jgarjgY8x5L2NKQoqIOmghuS9jeOCkuaxuuOCgeOCi+OCreODvOOBqOOBquOCi+WApOOBjOetieOBl+OBhOODh+ODvOOCv+OBr+OBmeOBueOBpuWQjOS4gOmghuS9jeOBqOOBquOCiwoqIDHkvY3ihpIy5L2N4oaSMuS9jSDjga7mrKHjga7lgKTjga7poIbkvY3jga805L2N44Go44Gq44KLCiopCgovLyBGIyA0LjDjgarjgonku6XkuIvjga7plqLmlbDjga7ku6Pjgo/jgorjgatTZXEuaW5kZXhlZOOBjOS9v+OBiOOCiwpsZXQgaW5kZXhlZCB4cyA9IHhzIHw+IFNlcS5tYXBpIChmdW4gaSB4IC0+IGksIHgpCgovLyBGIyA0LjDjgarjgonku6XkuIvjga7plqLmlbDjga7ku6Pjgo/jgorjgatTZXEubWFwRm9sZOOBjOS9v+OBiOOCiwpsZXQgbWFwRm9sZCBtYXBwaW5nIHN0YXRlIHhzID0KICAgIGxldCByZXN1bHQgPSAoKE5vbmUsIHN0YXRlKSwgeHMpIHx8PiBTZXEuc2NhbiAoZnVuIChfLCBzKSB4IC0+IGxldCBtLCBzID0gbWFwcGluZyBzIHggaW4gU29tZSBtLCBzKQogICAgKHJlc3VsdCB8PiBTZXEubWFwIGZzdCB8PiBTZXEuY2hvb3NlIGlkKSwgKHJlc3VsdCB8PiBTZXEubGFzdCB8PiBzbmQpCgovLyDplqLmlbDjga7mnKzkvZMKbGV0IHJhbmtlZCByYW5rUHJvamVjdGlvbiB4cyA9CiAgICBsZXQgcmFua01hcCA9CiAgICAgICAgbGV0IHNvcnRlZCA9IHhzIHw+IFNlcS5tYXAgcmFua1Byb2plY3Rpb24gfD4gaW5kZXhlZCB8PiBTZXEuc29ydEJ5IHNuZCB8PiBpbmRleGVkCiAgICAgICAgKCgxLCBOb25lKSwgc29ydGVkKSB8fD4gbWFwRm9sZCAoZnVuIChyLCBiKSAoYWksIChiaSwgaykpIC0+CiAgICAgICAgICAgIGxldCByYW5rID0gaWYgYiA9IFNvbWUgayB0aGVuIHIgZWxzZSBhaSArIDEKICAgICAgICAgICAgKGJpLCByYW5rKSwgKHJhbmssIFNvbWUgaykpCiAgICAgICAgfD4gZnN0IHw+IGRpY3QKICAgIHhzIHw+IExpc3QubWFwaSAoZnVuIGkgeCAtPiByYW5rTWFwLltpXSwgeCkKCi8vIOODhuOCueODiApsZXQgdGVzdCgpID0KICAgIGxldCBpbmxpbmUgc2hvdWxkQmUgZXhwZWN0ZWQgYWN0dWFsID0KICAgICAgICBpZiBleHBlY3RlZCA8PiBhY3R1YWwgdGhlbiBmYWlsd2l0aGYgImV4cGVjdGVkICVBLCBidXQgJUEiIGV4cGVjdGVkIGFjdHVhbAoKICAgIGxldCBzb3VyY2UgPSBbCiAgICAgICAgMywgMgogICAgICAgIDEsIDcKICAgICAgICA0LCAxCiAgICAgICAgMSwgOAogICAgICAgIDUsIDIKICAgICAgICA5LCA4CiAgICAgICAgMiwgMQogICAgXQogICAgbGV0IGV4cGVjdGVkID0gWwogICAgICAgIDQsICgzLCAyKQogICAgICAgIDEsICgxLCA3KQogICAgICAgIDUsICg0LCAxKQogICAgICAgIDEsICgxLCA4KQogICAgICAgIDYsICg1LCAyKQogICAgICAgIDcsICg5LCA4KQogICAgICAgIDMsICgyLCAxKQogICAgXQogICAgc291cmNlIHw+IHJhbmtlZCBmc3QgfD4gc2hvdWxkQmUgZXhwZWN0ZWQKICAgIHByaW50Zm4gInBhc3NlZC4iCgp0ZXN0KCk=