Выберите случайный элемент из взвешенного списка

Ответ 1

"Самый простой" способ справиться с этим - сохранить это в списке.

Затем вы можете просто использовать:

Name GetRandomName(Random random, List<Name> names)
{
    double value = random.NextDouble() * names[names.Count-1].Culmitive;
    return names.Last(name => name.Culmitive <= value);
}

Если скорость вызывает беспокойство, вы можете сохранить отдельный массив только значений Culmitive. При этом вы можете использовать Array.BinarySearch, чтобы быстро найти соответствующий индекс:

Name GetRandomName(Random random, List<Name> names, double[] culmitiveValues)
{
    double value = random.NextDouble() * names[names.Count-1].Culmitive;
    int index = Array.BinarySearch(culmitiveValues, value);
    if (index >= 0)
        index = ~index;

    return names[index];
}

Другим вариантом, который, вероятно, является наиболее эффективным, было бы использовать что-то вроде одной из C5 Generic Collection Library древовидные классы. Затем вы можете использовать RangeFrom для поиска соответствующего имени. Это имеет то преимущество, что не требуется отдельная коллекция

Ответ 2

Я создал библиотеку С# для случайно выбранных взвешенных элементов.

• Он реализует алгоритмы алгоритма выбора дерева и алгоритма walker alias, чтобы обеспечить максимальную производительность для всех случаев использования.
• Он тестируется и оптимизирован.
• Поддержка LINQ.
• Он бесплатный и с открытым исходным кодом, лицензированный по лицензии MIT.

Пример кода:

IWeightedRandomizer<string> randomizer = new DynamicWeightedRandomizer<string>();
randomizer["Joe"] = 1;
randomizer["Ryan"] = 2;
randomizer["Jason"] = 2;

string name1 = randomizer.RandomWithReplacement();
//name1 has a 20% chance of being "Joe", 40% of "Ryan", 40% of "Jason"

string name2 = randomizer.RandomWithRemoval();
//Same as above, except whichever one was chosen has been removed from the list.

Ответ 3

Я бы сказал, что массив (векторы, если вы предпочитаете) лучше всего их удерживать. Что касается взвешенного среднего значения, найдите сумму, выберите случайное число между нулем и суммой и выберите фамилию, суммарное значение которой меньше. (например, здесь < 1,006 = smith, 1,006-1,816 = johnson и т.д.

P.S. он кумулятивный.

Ответ 4

Просто для удовольствия и никоим образом не оптимальный

List<Name> Names = //Load your structure into this

List<String> NameBank = new List<String>();
foreach(Name name in Names)
   for(int i = 0; i <= (int)(name.Weight*1000); i++)
     NameBank.Add(name.Name)

то

String output = NameBank[rand(NameBank.Count)];