Взвешенный случайный выбор с заменой и без нее

В ответ на задачу программирования мы ищем эффективные алгоритмы для взвешенного случайного выбора из списка, как с заменой, так и без нее.

Взвешенный отбор с заменой

Один Эффективным методом взвешенного отбора с заменой является Метод псевдонимов. Этот метод создает набор ячеек одинакового размера для каждого взвешенного элемента. Используя битовые операции, мы можем эффективно индексировать эти ячейки, не прибегая к двоичному поиску. В каждом интервале хранится один процент, представляющий границу между исходными взвешенными элементами.

Рассмотрим пример пяти элементов с одинаковыми весами: (a, b, c, d, e).

Реализация метода псевдонима

1. Нормализация весов: разделите каждый вес на общую сумму, чтобы получить 1.0.
2. Определите наименьшую степень 2, большую или равную количеству элементов (здесь 8).
3. Назначьте каждому элементу пустой раздел.

4. Повторяйте следующие шаги, пока все веса не будут распределены:

   • Поместите как можно большую часть элемента с наименьшим оставшимся весом в пустое пространство. раздел.
   • Если раздел не заполнен, добавьте самый тяжелый оставшийся элемент.

Для нашего примера, после нескольких итераций, у нас есть следующий раздел:

• p1: {a, 1.0}
• p2: {a, b, 0.6}

Выбор времени выполнения

1. Сгенерируйте случайное число от 0 до 1.
2. Побитовый сдвиг случайного числа, чтобы найти индекс раздела.
3. Если раздел разделен, используйте десятичную часть сдвинутого побитового числа, чтобы решить, какой раздел возвращаемый элемент.

Взвешенный выбор без замены

Хотя такие алгоритмы, как метод взвешенного резервуара, существуют для невзвешенного выбора без замены, эта проблема остается нерешенной.