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

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() служит для нормализации диапазона аргументов. Возможно, эта нормализация не нужна для некоторых вариантов весовой функции.