Алгоритм для O (1) взвешенного случайного выбора с удалением

Question

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

К примеру, у меня есть пакет, который производит:

• Красный мрамор 70% времени.
• Зеленый мрамор 10% времени.
• И синий мрамор 20% времени.

Я пробовал сумку и получаю красный мрамор. Красный теперь удален, поэтому я предполагаю, что теперь будет создан мешок:

• Зеленый мрамор 33% времени.
• Голубой мрамор 66% времени.

Я считаю, что вы можете прекомпилировать дерево любой возможной таблицы вероятности, так что образец все еще O(1). Являются ли более умные алгоритмы для взвешенного по времени выбора с удалением?

Answer 1

На самом деле, кажется, я неправильно понял вопрос. Я не знал о методе псевдонимов, и нижеприведенный ответ не является аналогичным алгоритмом. Я оставлю свой ответ здесь, потому что он по-прежнему информативен.

---

Я не известно о O (1) алгоритма, но это легко сделать в журнале (N) поиска и журнала (N) обновление. Вероятно, это может быть улучшено с помощью более конкретного алгоритма.

Поместите свои элементы в Fenwick tree с их вероятностями в качестве их значений. Также при смене элементов учитывается общая кумулятивная вероятность.

Теперь мы можем делать все лучше, чем просто удалять элементы! Мы можем произвольно изменить вероятность элементов, но установка вероятности элемента на 0 эквивалентна его удалению. Затем можно запросить в log (N) кумулятивную вероятность n-й элемент. Это логически распространяется на журнал (N) двоичный поиск первого элемента с кумулятивной вероятностью, превышающей p.

Теперь, чтобы сделать взвешенный случайный выбор, мы генерируем число p между 0 и P, где P - общая кумулятивная вероятность. Затем мы выполняем описанный выше бинарный поиск, чтобы найти и выбрать первый элемент с кумулятивной вероятностью, превышающей p.

---

Я усовершенствовал выше, потому что использование дерева Фенвиков это легко сделать журнал (N) поиском первого элемента с кумулятивной probality большим или равным р. Я могу настоятельно рекомендовать прочитать this explanation of Fenwick trees.

Проще говоря, чтобы найти элемент, выполните регулярный двоичный поиск на дереве Фенвика, как и на любом другом дереве, за исключением того, что вы сохраняете текущую суммарную сумму (начиная с 0).Всякий раз, когда вы выбираете дочерний элемент правой руки в двоичном поиске, увеличивайте текущую суммарную сумму на значение текущего узла. Затем, сравнивая значение текущего узла с суммарной суммой, мы хотим добавить значение текущего узла к сумме до сравнения.