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

6

Updateмоя проблема была решена, я обновил код источника в своем вопросе, чтобы он соответствовал ответу Джейсона. Обратите внимание, что ответом rikitikitik является решение проблемы выбора карт из образца с заменой.

Я хочу выбрать x случайных элементов из взвешенного списка. Выборка без замены. Я нашел этот ответ:https://stackoverflow.com/a/2149533/57369 с реализацией в Python. Я реализовал это в C # и протестировал это. Но результаты (как описано ниже) не соответствовали моим ожиданиям. Я не знаю Python, поэтому я совершенно уверен, что допустил ошибку при переносе кода на C #, но не вижу, где код в Pythong действительно хорошо документирован.

Я выбрал одну карту 10000 раз, и вот результаты, которые я получил (результат одинаков для всех казней):

Card 1: 18.25 % (10.00 % expected)
Card 2: 26.85 % (30.00 % expected)
Card 3: 46.22 % (50.00 % expected)
Card 4: 8.68 % (10.00 % expected)

Как вы можете видеть, карта 1 и карта 4 имеют вес 1, но карта 1 выбирается намного чаще, чем карта 4 (даже если я выбираю 2 или 3 карты).

Тестовые данные:

var cards = new List<Card>
{
    new Card { Id = 1, AttributionRate = 1 }, // 10 %
    new Card { Id = 2, AttributionRate = 3 }, // 30 %
    new Card { Id = 3, AttributionRate = 5 }, // 50 %
    new Card { Id = 4, AttributionRate = 1 }, // 10 %
};

Вот моя реализация в C #

public class CardAttributor : ICardsAttributor
{
    private static Random random = new Random();

    private List<Node> GenerateHeap(List<Card> cards)
    {
        List<Node> nodes = new List<Node>();
        nodes.Add(null);

        foreach (Card card in cards)
        {
            nodes.Add(new Node(card.AttributionRate, card, card.AttributionRate));
        }

        for (int i = nodes.Count - 1; i > 1; i--)
        {
            nodes[i>>1].TotalWeight += nodes[i].TotalWeight;
        }

        return nodes;
    }

    private Card PopFromHeap(List<Node> heap)
    {
        Card card = null;

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

        while (gas >= heap[i].Weight)
        {
            gas -= heap[i].Weight;
            i <<= 1;

            if (gas >= heap[i].TotalWeight)
            {
                gas -= heap[i].TotalWeight;
                i += 1;
            }
        }

        int weight = heap[i].Weight;
        card = heap[i].Value;

        heap[i].Weight = 0;

        while (i > 0)
        {
            heap[i].TotalWeight -= weight;
            i >>= 1;
        }

        return card;
    }

    public List<Card> PickMultipleCards(List<Card> cards, int cardsToPickCount)
    {
        List<Card> pickedCards = new List<Card>();

        List<Node> heap = GenerateHeap(cards);

        for (int i = 0; i < cardsToPickCount; i++)
        {
            pickedCards.Add(PopFromHeap(heap));
        }

        return pickedCards;
    }
}

class Node
{
    public int Weight { get; set; }
    public Card Value { get; set; }
    public int TotalWeight { get; set; }

    public Node(int weight, Card value, int totalWeight)
    {
        Weight = weight;
        Value = value;
        TotalWeight = totalWeight;
    }
}

public class Card
{
    public int Id { get; set; }
    public int AttributionRate { get; set; }
}
System.Random - отличный генератор случайных чисел для этой цели. Конечно, это всего лишь генератор псевдослучайных чисел, но в данном случае это не проблема. Ruud
Воу, я бы сделал это с Linq,order by Guid.NewGuid() и удвоить / утроить / ... количество экземпляров согласно ставке. легче реализовать и легче читать - ни слова о производительности. Andreas Niedermair
@Adriano ты читал мой предыдущий комментарий? С помощью другого алгоритма я смог получить ожидаемое распределение при выборе одной карты 10 000 раз. Псевдослучайный генератор .NET НЕ является проблемой здесь. Gabriel
System.Random НЕ является хорошим генератором случайных чисел (и Guids вообще не является генератором случайных чисел). Если вам нужно настоящее случайное распределение, вы должны использовать что-то еще. Нет выбора. Adriano Repetti
Примечание: даже для «идеального» СЧИТАЕТ, что вы не получите одинаковое количество попаданий для обеих карт (даже если они имеют одинаковый вес) ... Adriano Repetti

Ваш Ответ

4   ответа
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();

И выбрать х карт:

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% 

РЕДАКТИРОВАТЬ:

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

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

Боюсь, я плохо сформулировал свой вопрос: как только карта выбрана, вы не можете выбрать ее снова (это я и имел в виду под образцом без замены, цемент). Несмотря на то, что ваш первоначальный ответ полностью учитывал вес, он также получал дубликаты карточек, которые не соответствуют моим требованиям. Gabriel
Я пытался увидеть, где твой код пошёл не так, но побитовые операции запали мне в голову;
Да, это так, сократило время вычислений чуть более чем на 40%, но все же намного медленнее, чем оригинальное решение. Ответ, с которого я скопировал свой код, был проголосован 28 раз, поэтому я полагаю, что он работает так, как рекламируется. Я не понимаю, как мой код может быть таким неправильным. Gabriel
Я не знал, что производительность - это соображение.Guid.NewGuid() частьmay будь виновником и тыmay получите лучший результат, генерируя здесь случайные десятичные дроби. Хотя я не уверен на 100% в этом.
Ваш код работает, поэтому я думаю принять это как ответ. Но это в 6 раз медленнее, чем код, который я разместил, и я уверен, что разница будет еще больше, когда я начну работать с реальными данными. Gabriel
0

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);
}

Теоретически это должно работать.

Я не проверял его код, но думаю, что большая проблема не в том, КАК вы "извлекаете" карта, но способ, которым вы генерируете псевдослучайное число. Встроенный генератор далеко не оптимален.
Вот результаты, которые я получаю с вашим решением: карта 1: 0,00% (ожидается 10,00%), карта 2: 0,00% (ожидается 30,00%), карта 3: 0,00% (ожидается 50,00%), карта 4: 100,00% (10,00) % ожидается). Эта проблема не так тривиальна, как кажется, пожалуйста, обратитесь к ссылке вопрос (stackoverflow.com/a/2149533/57369), чтобы получить больше понимания. Gabriel
1

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

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

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

Один алгоритм, который выполняет это, состоит в том, чтобы выстроить элементы вдоль числовой линии от 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

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

2

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

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

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

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

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

На самом деле я говорил слишком быстро, это работает безупречно, когда я выбираю только одну карту. Как только я выбираю несколько карт (например, 3 с данным набором), я получаю следующий результат: Карта 1: 18,30% (ожидается 10,00%), Карта 2: 30,20% (ожидается 30,00%), Карта 3: 32,25% ( Ожидается 50,00%), карта 4: 19,25% (ожидается 10,00%) Gabriel
Спасибо, это имеет полный смысл. Я попытался с несколькими различными образцами и выбрать количество, и результат кажется удовлетворительным :) Gabriel
@ Габриэль Я не думаю, что ваши ожидания правильны в отношении выбора нескольких карт. В каждом испытании вы выбираете 3 карты без замены, верно? Таким образом, карта 3 не может составлять 50% пиков!
Когда вы выбираете несколько карт без замены, вероятности меняются по мере продвижения. После удаления первой карты вероятность выбора этой карты снова становится равной 0, а вероятность выбора оставшихся карт возрастает. Если вы выберете 3 из этих 4 карт без замены, я ожидаю, что вы получите Карту 3 примерно в 96,6% случаев. Но так как это только одна из трех выбранных вами карт, она составляет всего 32,2% от общего количества ваших пиков. Обратите внимание, что это очень близко к тому, что вы наблюдали!

Похожие вопросы