Случайный выбор, взвешенный по сравнению с недавними предыдущими выборами

Question

Я хотел бы выбрать элемент списка, в котором каждый элемент имеет вес, как долго он был выбран последним.

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

Простое вычитание или разделение веса на определенную величину после его выбора не кажется интуитивно правильным. Есть ли лучший способ, возможно, использовать математическую концепцию, такую ​​как логарифмы или инверсии? (Не мой конек)

Answer 1

Как о чем-то вроде этого:

Пусть n = число элементов, list = массив элементов, watermark: = 0.

r := random() 
i := floor(r * n) 

if i >= watermark : 
    index := i 
    watermark := watermark + 1 // weighted part grows 
else : 
    index := floor(weight(r * n/watermark) * watermark) 
endif 

move list[index] to list[0]  // shifting elements list[0..index-1] up one place 
result := list[0] 

Здесь мы разделим список на две части, взвешенные и однородные, с границей, отслеживаемой watermark. Первоначально взвешенная часть пуста, но постепенно она растет, в конечном итоге потребляет весь список.

random() - это функция, которая возвращает случайное число в [0.0, 1.0].

weight(x) является функцией от [0.0, 1.0] до [0.0, 1.0], которая определяет требуемое взвешивающее поведение.

«r * n/watermark» в качестве аргумента weight() служит для нормализации диапазона аргументов. Возможно, эта нормализация не нужна для некоторых вариантов весовой функции.