Recently in algo Category

Дано:

Массив длиной L, каждый элемент массива имеет вес weight (для простоты - целочисленный)

Задача:

Выбрать рандомно N элементов из массива (N < L), при этом не должно быть одинаковых элементов, и вероятность выборки каждого элемента должна быть прямо пропорциональна весу элемента.

Решение:

Разместим элементы массива на оси весов, при этом длина отрезка каждого элемента равна весу этого элемента.
Посчитаем суммарный вес элементов - это максимально возможная координата.

Теперь итерируем массив от начала (столько итераций, сколько нужно выбрать элементов). На каждой итерации:

• Выбираем рандомно точку от 1 до макс. координаты $weight
• Ищем элемент, соответствующий отрезку, содержащему эту точку
• Меняем местами выбранный элемент с элементом, соответствующем текущей итерации - т.о. "запоминаем" его.
• Сдвигаем начало координат (и соотв. макс. координату) на величину, равную длине отрезка выбранного элемента

Всё. Теперь N начальных элементов - и есть интересующая нас выборка. Осталось только отбросить лишнюю часть массива от N+1 до L

# @res - исходный массив
# $need_count - сколько нужно выбрать элементов
# $weight - суммарный вес всех элементов исходного массива

for (my $i=0; $i<$need_count; $i++) {
    my $w = int(rand $weight)+1; # выбираем точку на оси весов
    for (my $j=$i; $j<=$#res; $j++) { # ищем элемент, соотв. точке
        if ($res[$j]->{weight} >= $w) {
            $weight -= $res[$j]->{weight};
            ($res[$i], $res[$j]) = ($res[$j], $res[$i]) if $i != $j;
            last;
        } else {
            $w -= $res[$j]->{weight};
        }
    }
}
@res = splice(@res,0,$need_count); # обрезаем массив