問題描述
更新:我的問題已解決，我更新了問題中的代碼源以與 Jason 的回答相匹配.請注意，rikitikitik 的答案是解決從樣本中抽取卡片并替換的問題.
Update: my problem has been solved, I updated the code source in my question to match with Jason's answer. Note that rikitikitik answer is solving the issue of picking cards from a sample with replacement.
我想從加權列表中選擇 x 個隨機元素.采樣是無更換的.我找到了這個答案:https://stackoverflow.com/a/2149533/57369 用 Python 實現.我在 C# 中實現了它并對其進行了測試.但是結果(如下所述)與我的預期不符.我對 Python 一無所知，所以我很確定我在將代碼移植到 C# 時犯了一個錯誤，但我看不到 Pythong 中的代碼在哪里有很好的文檔記錄.
I want to select x random elements from a weighted list. The sampling is without replacement. I found this answer: https://stackoverflow.com/a/2149533/57369 with an implementation in Python. I implemented it in C# and tested it. But the results (as described below) were not matching what I expected. I've no knowledge of Python so I'm quite sure I made a mistake while porting the code to C# but I can't see where as the code in Pythong was really well documented.
我選擇了一張卡片 10000 次，這是我得到的結果(結果在執行中是一致的):
I picked one card 10000 times and this is the results I obtained (the result is consistent accross executions):
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 張卡片).
As you can see Card 1 and Card 4 have both a weigth of 1 but Card 1 is awlays picked way more often than card 4 (even if I pick 2 or 3 cards).
測試數據:
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# 中的實現
Here is my implementation in 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; }
}
推薦答案
程序中有兩個小錯誤.首先，隨機數的范圍應該正好等于所有物品的總重量:
There are two minor bugs in the program. First, the range of the random number should be exactly equal to the total weight of all the items:
int gas = random.Next(heap[1].TotalWeight);
其次，將 gas > 的兩個地方都改為 gas >=.
Second, change both places where it says gas > to say gas >=.
(原Python代碼可以，因為gas是浮點數，所以>和>=的區別可以忽略不計.編寫該代碼是為了接受整數或浮點權重.)
(The original Python code is OK because gas is a floating-point number, so the difference between > and >= is negligible. That code was written to accept either integer or floating-point weights.)
更新:好的，您在代碼中進行了建議的更改.我認為該代碼現在是正確的！
Update: OK, you made the recommended changes in your code. I think that code is correct now!
這篇關于從 C# 中的加權列表中選擇 x 個隨機元素(無需替換)的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！