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); # обрезаем массив

About this Archive

This page is an archive of recent entries in the algo category.

apache is the next category.

Find recent content on the main index or look in the archives to find all content.

Pages

Powered by Movable Type 4.2-en