Wählen Sie x zufällige Elemente aus einer gewichteten Liste in C # (ohne Ersetzung)
Aktualisieren: Mein Problem wurde gelöst. Ich habe die Codequelle in meiner Frage aktualisiert, damit sie mit Jasons Antwort übereinstimmt. Beachten Sie, dass die Antwort von rikitikitik das Problem des Entnehmens von Karten aus einem Muster mit Ersatz löst.
Ich möchte x zufällige Elemente aus einer gewichteten Liste auswählen. Die Bemusterung ist ersatzlos. Ich habe diese Antwort gefunden:https://stackoverflow.com/a/2149533/57369 mit einer Implementierung in Python. Ich habe es in C # implementiert und getestet. Aber die Ergebnisse (wie unten beschrieben) stimmten nicht mit meinen Erwartungen überein. Ich kenne Python nicht und bin mir ziemlich sicher, dass ich beim Portieren des Codes nach C # einen Fehler gemacht habe, aber ich kann nicht erkennen, wo der Code in Pythong wirklich gut dokumentiert war.
Ich habe 10000 Mal eine Karte ausgewählt und dies sind die Ergebnisse, die ich erhalten habe (das Ergebnis ist konsistent über die Ausführungen hinweg):
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)
Wie Sie sehen, haben Karte 1 und Karte 4 beide ein Gewicht von 1, aber Karte 1 wird viel häufiger als Karte 4 ausgewählt (auch wenn ich 2 oder 3 Karten auswähle).
Testdaten:
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 %
};
Hier ist meine Implementierung 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; }
}