алгоритм выбора множества победителей с использованием разных весов

Question

Я пытаюсь разработать алгоритм, который делает следующее.

Ввод:

У меня есть набор ключей (всего n), которые сопоставлены с набором свойств.Свойства содержат вес для каждого свойства и значение для свойства.

Вывод:

Определение набора квалифицированных ключей (всего k) на основе набора свойств и их соответствующих весов и значений.

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

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

Любая информация о том, как это можно сделать, будет принята с благодарностью.

Спасибо!- Азим

Answer 1

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

Удалите этого победителя и соответственно уменьшите общую длину линии. Затем повторите процесс с остальными кандидатами, пока не выберете свой k.

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

Answer 2

неоптимизированный, но эффективный метод - составить список всех участников, но добавить дополнительные индексы для контеста, пропорциональные весу.

psuedo полностью выходит за рамки любой реальной реализации, но вы должны понять.

const int DEFAULT_WEIGHT = 1;
public List<Contestant> items = new List<Contestant>();
public List<Guid> LotteryPool = new List<int>();

public Contestant Roll()
{
     Random rnd = new Random();
     rnd.Seed = DateTime.Now.Ticks;

     // Generate LotteryPool
     foreach(Contestant item in items)
     {
              for(int i = 0; i < item.Weight; i++)
              {
                       LotteryPool.Add(item.Id);
              }

              item.Weight++;
     }

     // Find the contestant matching a random id from the pool.
     Contestant result = FindContestant(LotteryPool[rnd.Next(0, LotterPool.Count]);

     // apply the default weight the winner
     result.Weight = DEFAULT_WEIGHT;

     return result;
}