我有一个加权选择算法是有效的，但我想在两个方面改进它（按重要性顺序）：
简化代码：
函数
解决问题＃1（保证选择每个可能选择的最小数量）的第一个想法是以完全非随机的方式选择每个类型所需的最小值，使用现有算法选择剩余的无限制部分，然后将结果混合在一起。这似乎是最自然的，并模拟了我在现实生活中做此类事情的方式，但我认为这不是最有效的方法。
我的第二个想法是先创建结果数组，首先随机选择填充所需最小值的索引，然后使用现有算法填充其余部分，但在所有尝试中，这都会增加“大O”复杂度或记录索引的混乱大乱炖。我仍然认为这种方法是可行的，但我还没有能够解决它。
然后我决定来这里，因为这个问题似乎可以抽象成一个相当通用的算法，但我使用的所有关键字通常指向基本的加权随机数生成（而不是选择具有特定可用性的类型组中的离散项，并且每个项目类型都至少选择一项）。我还没有能够找到任何限制带有每个项目类型的最小选择的问题，同时仍然保持随机化的内容。因此，我希望聪明的人可以看到一个简单高效的解决方案，或者听说过这个问题的人知道比我更好的关键字，并可以指引我正确的方向。
- 保证每个可能的选择都选取了最少数量。
- 将计算复杂度从 O(nm) 降至 O(n) 或 O(m)，其中 n 是请求随机选择项目的数量，m 是可用项目的类型。
简化代码：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Security.Cryptography;
public class Program
{
static void Main(string[] args)
{
// List of items with discrete availability
// In this example there is a total of 244 discrete items and 3 types,
// but there could be millions of items and and hundreds of types.
List<Stock<string>> list = new List<Stock<string>>();
list.Add(new Stock<string>("Apple", 200));
list.Add(new Stock<string>("Coconut", 2));
list.Add(new Stock<string>("Banana", 42));
// Pick 10 random items
// Chosen with equal weight across all types of items
foreach (var item in Picker<string>.PickRandom(10, list))
{
// Do stuff with item
Console.WriteLine(item);
}
}
}
// Can be thought of as a weighted choice
// where (Item Available) / (Sum of all Available) is the weight.
public class Stock<T>
{
public Stock(T item, int available)
{
Item = item;
Available = available;
}
public T Item { get; set; }
public int Available { get; set; }
}
public static class Picker<T>
{
// Randomly choose requested number of items from across all stock types
// Currently O(nm), where n is requested number of items and m is types of stock
// O(n) or O(m) would be nice, which I believe is possible but not sure how
// O(1) would be awesome, but I don't believe it is possible
public static IEnumerable<T> PickRandom(int requested, IEnumerable<Stock<T>> list)
{
// O(m) : to calcuate total items,
// thus implicitly have per item weight -> (Item Available) / (Total Items)
int sumAll = list.Sum(x => x.Available);
// O(1)
if (sumAll < requested)
throw new ArgumentException("Requested amount must not exceed total available");
// O(1)
Random rng = new Random(Seed());
// O(n) for the loop alone : O(nm) total
for (int n = 0; n < requested; n++)
{
// O(1) to choose an item : uses implicit ordering
int choice = rng.Next(1, sumAll);
int current = 0;
// O(m) to find the chosen item
foreach (Stock<T> stock in list)
{
current += stock.Available;
if (current >= choice)
{
yield return stock.Item;
// O(1) to re-calculate weight once item is found
stock.Available -= 1;
sumAll--;
break;
}
}
}
}
// Sufficiently random seed
private static int Seed()
{
byte[] bytes = new byte[4];
new RNGCryptoServiceProvider().GetBytes(bytes);
return bytes[0] << 24 | bytes[1] << 16 | bytes[2] << 8 | bytes[3];
}
}
函数
PickRandom()使用yield return和IEnumerable，但并不是必需的。我最初编写该函数时只是想聪明一些，以便可以迭代任何东西（甚至来自LINQ到SQL查询的可枚举对象）。后来，我发现虽然灵活性很好，但我从未真正需要它。解决问题＃1（保证选择每个可能选择的最小数量）的第一个想法是以完全非随机的方式选择每个类型所需的最小值，使用现有算法选择剩余的无限制部分，然后将结果混合在一起。这似乎是最自然的，并模拟了我在现实生活中做此类事情的方式，但我认为这不是最有效的方法。
我的第二个想法是先创建结果数组，首先随机选择填充所需最小值的索引，然后使用现有算法填充其余部分，但在所有尝试中，这都会增加“大O”复杂度或记录索引的混乱大乱炖。我仍然认为这种方法是可行的，但我还没有能够解决它。
然后我决定来这里，因为这个问题似乎可以抽象成一个相当通用的算法，但我使用的所有关键字通常指向基本的加权随机数生成（而不是选择具有特定可用性的类型组中的离散项，并且每个项目类型都至少选择一项）。我还没有能够找到任何限制带有每个项目类型的最小选择的问题，同时仍然保持随机化的内容。因此，我希望聪明的人可以看到一个简单高效的解决方案，或者听说过这个问题的人知道比我更好的关键字，并可以指引我正确的方向。