古い記事
ランダムジャンプ
新しい記事
問題設定:
複数の要素をそれぞれが持つある値(val)の降順でソートする。
当り前だが同じ値を持つ要素があれば隣同士になる。
で、トップに同じ値を持つ要素が複数ある場合にその中からランダムで一つだけピックアップしたい。

解法:
ソート後に「ファイルから行をランダムに取り出す手法」[2004-11-30-5]を適用する。
リスト末にたどりつくか値が変わったらループ終了。

■サンプルコード(randomtop.pl):
#!/usr/bin/perl
use strict;
use warnings;

my @list =  (1,2,1,3,3,2,2,1,3,1,3,2);

my @a0 = map {{rank => chr(65+int(rand(6))), val => $_}} @list;
my @a1 = sort {$b->{val} <=> $a->{val}} @a0;
my @a2 = sort {$b->{val} <=> $a->{val} or $a->{rank} cmp $b->{rank}} @a0;

print "DEFAULT:     ".join(" ", map {"$_->{val}:$_->{rank}"} @a0)."\n";
print "SORT_BY_VAL: ".join(" ", map {"$_->{val}:$_->{rank}"} @a1)."\n";
print "BY_VAL_RANK: ".join(" ", map {"$_->{val}:$_->{rank}"} @a2)."\n";

my $sel = $a2[0];
for (my $i = 1; $i <@a2 and $a2[$i-1]{val} == $a2[$i]{val}; $i++) {
  rand($i+1) < 1 && ($sel = $a2[$i]);
}
print "RANDOM_TOP: $sel->{val}:$sel->{rank}\n";

■実行例:
% ./randomtop.pl                                  
DEFAULT:     1:B 2:F 1:B 3:D 3:D 2:E 2:B 1:B 3:B 1:B 3:E 2:A
SORT_BY_VAL: 3:D 3:D 3:B 3:E 2:F 2:E 2:B 2:A 1:B 1:B 1:B 1:B
BY_VAL_RANK: 3:B 3:D 3:D 3:E 2:A 2:B 2:E 2:F 1:B 1:B 1:B 1:B
RANDOM_TOP: 3:D

% ./randomtop.pl
DEFAULT:     1:A 2:B 1:A 3:C 3:A 2:E 2:D 1:E 3:E 1:A 3:D 2:F
SORT_BY_VAL: 3:C 3:A 3:E 3:D 2:B 2:E 2:D 2:F 1:A 1:A 1:E 1:A
BY_VAL_RANK: 3:A 3:C 3:D 3:E 2:B 2:D 2:E 2:F 1:A 1:A 1:A 1:E
RANDOM_TOP: 3:A

% ./randomtop.pl
DEFAULT:     1:A 2:B 1:E 3:F 3:C 2:B 2:D 1:C 3:D 1:D 3:E 2:C
SORT_BY_VAL: 3:F 3:C 3:D 3:E 2:B 2:B 2:D 2:C 1:A 1:E 1:C 1:D
BY_VAL_RANK: 3:C 3:D 3:E 3:F 2:B 2:B 2:C 2:D 1:A 1:C 1:D 1:E
RANDOM_TOP: 3:F

SORT_BY_VAL は val の値の降順でソート。
BY_VAL_RANK は val の値でのソートなんだけど同じ値のときは rank の昇順でソート。
RANDAM_TOP は最大 val 値を持つ中からランダムで一つ選択したもの。