logo标签列表

在C#中从一个加权列表中随机选择x个元素（不重复）

c#statisticsprobability
7
更新：我的问题已经解决，我更新了我的问题中的代码源以与Jason的答案匹配。请注意，rikitikitik的答案是解决从带替换的样本中选择卡片的问题。
我想从加权列表中选择x个随机元素。采样是不重复的。我找到了这个回答：https://dev59.com/D3I95IYBdhLWcg3wzhd9#2149533，其中包含Python的实现。我在C#中实现并测试了它。但结果（如下所述）与我预期的不符。我对Python一无所知，因此我确定我在将代码移植到C#时犯了错误，但我看不出来，因为Python中的代码非常好文档化。
我选择了一张卡片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，但是无论我选2张还是3张卡片，卡片1总是比卡片4被选中的次数多得多。

测试数据：

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不是一个好的随机数生成器（而Guid根本不是随机生成器）。如果您需要真正的随机分布，您必须使用其他东西。别无选择。 - Adriano Repetti
如果您想要按照该比例精确提取卡片，则只需根据该比例生成卡片，然后混合它们。 - Adriano Repetti
7
对于这个目的，System.Random是一个完全可以胜任的随机数生成器。当然它只是一个伪随机数生成器，但在这种情况下这并不是问题。 - Ruud
2
@Adriano，你看到我之前的评论了吗？使用另一个算法，我成功地在抽取一张牌 10,000 次时得到了预期的分布。.NET 的伪随机生成器在这里并不是问题所在。 - Gabriel
@Gabriel 我猜我们在谈论不同的事情！天真的方法是：选择一个随机整数 [0..100)，将前10个槽分配给卡片1，将接下来的30个槽分配给卡片2（以此类推）。你会得到一个天真的“加权”随机数生成器。问题在于分布和可预测性有些错误，但是... 我同意，在这种情况下 System.Random 将满足他的需求！！！ - Adriano Repetti
显示剩余6条评论
4个回答
3

正如一些人在评论中提到的那样，按照你想要的确切比例创建卡片列表：

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%

编辑：

我勇敢地进行了位运算，并查看了您的代码。在我的炸脑中添加了大量的烧烤酱后，我注意到了一些事情：

首先，Random.Next(min,max)将包括min在随机池中，但不包括max。这就是Card 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%

然而，由于这个语句的存在，当您抽取多张卡牌时，您的代码将无法正常工作：

heap[i].Weight = 0;

那行代码以及之后的重新计算循环，本质上是从堆中删除所有已抽出的卡牌。如果你恰好抽出了四张卡牌，那么所有卡牌的百分比就变成了25%，因为你基本上抽出了全部4张卡牌。然而，这个算法并不完全适用于你的情况。
我猜想，每次抽卡时你可能需要重新创建堆，但我怀疑它的性能会下降。如果我要处理这个问题，我会从1到heap[1].TotalWeight生成4个不同的随机数，并从中获取相应的4张卡牌，尽管在这种情况下随机数生成可能会变得不可预测（重新投掷），因此效率会降低。
你的代码可以工作，所以我考虑接受它作为答案。但是它比我发布的代码慢了6倍，而且我相信一旦我开始处理真实数据，差距甚至会更大。 - Gabriel
我不知道性能是一个考虑因素。Guid.NewGuid() 部分可能是罪魁祸首，你可以在这里生成随机小数以获得更好的结果。虽然我不能百分之百确定。 - rikitikitik
是的，它确实将计算时间缩短了40%以上，但仍然比原始解决方案慢得多。我复制代码的答案获得了28个赞，所以我想它应该像广告中说的那样工作。我不明白我的代码怎么会这么错。 - Gabriel
1
我试图找出你的代码哪里出了问题，但是位运算让我的大脑变得一团糟。 ;) - rikitikitik
很抱歉，我表达不清楚：一旦选择了一张卡片，就不能再次选择它（这就是我所说的无重复样本）。尽管您最初的答案完全尊重了权重，但也会得到重复的卡片，这与我的要求不符。 - Gabriel
3
程序中有两个小bug。首先，随机数的范围应该完全等于所有项目的总权重：
int gas = random.Next(heap[1].TotalWeight);

其次，将两个地方中的gas >都改为gas >=。

(原始的Python代码没有问题，因为gas是一个浮点数，所以>和>=之间的差异可以忽略不计。该代码编写成接受整数或浮点数权重的形式。)

更新：好的，你已经在你的代码中进行了推荐的更改。我认为该代码现在是正确的！

实际上，我说话太快了。当我只选一张卡时，它可以完美运行。但是，一旦我选择多张卡（例如在给定的套牌中选择3张），我会得到以下结果： 卡片1：18.30％（期望值为10.00％），卡片2：30.20％（期望值为30.00％），卡片3：32.25％（期望值为50.00％），卡片4：19.25％（期望值为10.00％）。 - Gabriel
@Gabriel，我认为你对于选择多张卡牌的期望不正确。在每次尝试中，你是不重复地选择3张卡牌，对吧？因此，第三张卡牌不可能占据50%的选择比例！ - Jason Orendorff
1
当你不重复地选择多张卡片时，随着选择的进行，概率会发生变化。一旦你移除第一张卡片，再次选择该卡片的概率将变为0，而选择剩余卡片的概率将增加。如果你不重复地选择其中4张卡片中的3张，我预计你会在96.6%的时间里得到第三张卡片。但由于它只是你选择的三张卡片中的一张，因此它仅占你总选择次数的32.2%。请注意，这非常接近你观察到的结果！ - Jason Orendorff
谢谢，这很有道理。我尝试了几个不同的样本和选取计数，结果看起来令人满意 :) - Gabriel
1
如果你想从一个加权集合中不重复地选择x个元素，使得元素被选择的概率与它们的权重成比例，那么你的算法是错误的。
考虑以下加权列表： 'a'：权重1 'b'：权重2 'c'：权重3 并且x = 2
在这个例子中，你的函数应该总是在结果集中返回'c'。这是唯一的方式让'c'被选中3倍于'a'和1.5倍于'b'。但很容易看出你的算法并不总是返回'c'。
一种实现这个目标的算法是将项目沿着从0到1的数轴上排列，使它们占据一个大小与其权重成比例的段，然后随机选择一个介于0和1/x之间的数字“start”，然后找到所有点“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

注意：这只适用于最大权重小于等于步长的情况。如果其中一个元素的权重大于总重量/x，则此问题无法解决：您必须多次选择某个元素以尊重权重。
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);
}

理论上这应该可以工作。

我没有检查过他的代码，但我猜测大问题不在于你如何“提取”卡片，而是你生成伪随机数的方式。内置生成器远非最佳选择。 - Adriano Repetti
这是使用您的解决方案得到的结果：卡1：0.00％（期望10.00％），卡2：0.00％（期望30.00％），卡3：0.00％（期望50.00％），卡4：100.00％（期望10.00％）。这个问题并不像看起来那么简单，请参考链接问题（https://dev59.com/D3I95IYBdhLWcg3wzhd9#2149533）以获得更多见解。 - Gabriel
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接