Выберите x случайных элементов из взвешенного списка в С# (без замены)

Ответ 1

В программе есть две незначительные ошибки. Во-первых, диапазон случайного числа должен быть в точности равен общему весу всех предметов:

int gas = random.Next(heap[1].TotalWeight);

Во-вторых, измените оба места, где говорится gas >, чтобы сказать gas >=.

(Исходный код Python в порядке, потому что gas - число с плавающей запятой, поэтому разница между > и >= незначительна. Этот код был написан для принятия либо целых, либо с плавающей запятой.)

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

Ответ 2

Как некоторые люди упомянули в комментариях, создайте список карт в той точной пропорции, которую вы хотите:

var deck = new List<Card>();

cards.ForEach(c => 
{
    for(int i = 0; i < c.AttributionRate; i++)
    {
         deck.Add(c);
    }
}

В случайном порядке:

deck = deck.OrderBy(c => Guid.NewGuid()).ToList();

И выберите x карты:

var hand = deck.Take(x)

Конечно, это работает только в том случае, если AttributionRate является int. В противном случае вам придется немного поработать с колодой.

Я получаю следующие результаты для 10 000 прогонов, принимающих 5 за раз:

Card 1: 9.932% 
Card 2: 30.15% 
Card 3: 49.854% 
Card 4: 10.064% 

Другой результат:

Card 1: 10.024%
Card 2: 30.034%
Card 3: 50.034% 
Card 4: 9.908% 

EDIT:

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

Во-первых, Random.Next(min,max) будет включать min в случайном пуле, но не max. Это является причиной более высокой, чем ожидалось, вероятности для карты 1.

После выполнения этого изменения я внедрил ваш код и, похоже, работает, когда вы рисуете 1 карту.

Card 1: 10.4%  
Card 2: 32.2% 
Card 3: 48.4% 
Card 4: 9.0% 

Card 1: 7.5%
Card 2: 28.1%
Card 3: 50.0% 
Card 4: 14.4% 

ОДНАКО, ваш код не будет работать, если вы рисуете более 1 карты из-за этого утверждения:

heap[i].Weight = 0;

Эта строка и цикл пересчета после этого существенно удаляют все экземпляры извлеченной карты из кучи. Если вам выпадет четыре карты, тогда процент будет составлять 25% для всех карт, так как вы в основном рисуете все 4 карты. Алгоритм, как есть, не полностью применим к вашему делу.

Я подозреваю, что вам придется воссоздавать кучу каждый раз, когда вы рисуете карту, но я сомневаюсь, что она все равно будет работать. Если бы я работал над этим, я бы просто сгенерировал 4 разных случайных числа от 1 до heap[1].TotalWeight и получил от них 4 соответствующие карты, хотя генерация случайных чисел в этом случае могла бы стать непредсказуемой (перерисовкой) и, следовательно, неэффективной.

Ответ 3

Если вы хотите выбрать х элементов из взвешенного набора без замены, чтобы элементы выбирались с вероятностью, пропорциональной их весам, то ваш алгоритм ошибочен.

Рассмотрим следующий взвешенный список:
'a': вес 1
'b': вес 2
'c': вес 3
и x = 2

В этом примере ваша функция всегда должна возвращать 'c' в наборе результатов. Это единственный способ, чтобы "c" выбирался в 3 раза чаще, чем "a", и в 1,5 раза чаще, чем "b". Но тривиально видеть, что ваш алгоритм не всегда дает результат "c".

Один алгоритм, который выполняет это, состоит в том, чтобы выровнять элементы вдоль числовой строки от 0 до 1 так, чтобы они занимали сегмент, пропорциональный их весу, затем случайным образом выбирали число "начало" между 0 и 1/x, затем найти все точки "start + n/x" (для всех целых чисел n, таких, что точка находится между 0 и 1) и дать множество, содержащее элементы, отмеченные этими точками.

Другими словами, что-то вроде:

a.) optionally shuffle the list of elements (if you need random combinations of elements in addition to respecting the weights)  
b.) create a list of cumulative weights, if you will, called borders, such that borders[0] = items[0].weight and borders[i] = borders[i - 1] + items[i].weight  
c.) calculate the sum of all the weights => total_weight  
d.) step_size = total_weight / x  
e.) next_stop = pick a random number between [0, step_size)  
f.) current_item = 0  
g.) while next_stop < total_weight:
h.)   while borders[current_item] < next_stop:  
i.)     current_item += 1  
j.)   append items[current_item] to the output  
k.)   next_stop += step_size

Примечание: это работает только там, где наибольший вес <= step_size. Если один из элементов имеет вес больше общего веса /x, то эта проблема невозможна: вам нужно будет выбрать элемент более одного раза, чтобы уважать веса.

Ответ 4

Вы можете сделать это:

Card GetCard(List<Card> cards)
{
  int total = 0;
  foreach (Card c in cards)
  {
    total += AttributionRate;
  }

  int index = Random.Next(0, total - 1);
  foreach(Card c in cards)
  {
    index -= c.AttributionRate;
    if (index < 0)
    {
      return c;
    }
  }
}

Card PopCard(List<Card> cards)
{
  Card c = GetCard(cards);
  cards.Remove(c);
}

В теории это должно сработать.