random number generation with weight

Question

I am looking for generating 4 random numbers, between 1 and 10, with weight assigned to each number. For example:

number   weight
  1        3
  2        2
  3        6
 ...      ...
 10        3

I saw some articles on this (one on this site: https://softwareengineering.stackexchange.com/questions/150616/return-random-list-item-by-its-weight) but it doesn't exactly do what need. I need to generate 4 numbers between 1 and 10, without replacement; can't have 2,3,8,2.

Answer 1

To generate the numbers without repition. I'll advice adding the numbers to a list and removing already shown numbers. Like this

List<int> nos = new List<int>(10);
nos.Add(1); nos.Add(2); nos.Add(3); nos.Add(4); nos.Add(5); 
nos.Add(6); nos.Add(7); nos.Add(8); nos.Add(9); nos.Add(10);
Random rnd = new Random();
int n1 = rnd.Next(nos.Count);
Console.WriteLine(nos[n1].ToString());
nos.RemoveAt(n1);
int n2 = rnd.Next(nos.Count - 1);
Console.WriteLine(nos[n2].ToString());
nos.RemoveAt(n2);
int n3 = rnd.Next(nos.Count - 2);
Console.WriteLine(nos[n3].ToString());
nos.RemoveAt(n3);
int n4 = rnd.Next(nos.Count - 3);
Console.WriteLine(nos[n4].ToString());
nos.RemoveAt(n4);

Answer 2

This is what i think, rather a programmer way than statistic/math. List of numbers with weight:

number   weight
  1        3
  2        2
  3        6
...      ...
  9        3
 10        3

The program will choose random index of List, and pick the number in the List at that chosen index. Weight of a number simulated by adding that number to the List as much as the weight. This is the main method (and thanks for @Tijesunimi as i'm using part of code in his answer with little correction):

List<int> nos = new List<int>(10);
nos.AddWeightedNo(1, 3);
nos.AddWeightedNo(2, 2);
nos.AddWeightedNo(3, 6);
//...
nos.AddWeightedNo(9, 3);
nos.AddWeightedNo(10, 3);
Random rnd = new Random();
int n1 = rnd.Next(nos.Count);
Console.WriteLine(nos[n1].ToString());
nos.RemoveWeightedNo(nos[n1]);
int n2 = rnd.Next(nos.Count);
Console.WriteLine(nos[n2].ToString());
nos.RemoveWeightedNo(nos[n2]);
int n3 = rnd.Next(nos.Count);
Console.WriteLine(nos[n3].ToString());
nos.RemoveWeightedNo(nos[n3]);
int n4 = rnd.Next(nos.Count);
Console.WriteLine(nos[n4].ToString());
nos.RemoveWeightedNo(nos[n4]);

And the extension methods AddWeightedNo and RemoveWeightedNo:

public static class Extension
{
    public static void AddWeightedNo(this List<int> nos, int no, int weight)
    {
        for (int i = 0; i < weight; i++)
        {
            nos.Add(no);
        }
    }

    public static void RemoveWeightedNo(this List<int> nos, int no)
    {
        nos.RemoveAll(o => o == no);
    }
}

Answer 3

"I" have solved this in other languages by implementing bitwise search algorithm. There are a few examples around the net, even on stack overflow - but for other languages only I guess.

I'll need one myself so chances are I'll post the code here later when I'm ready.

Bitwise search is not maybe the fastest out there, but it's fast enough for most cases and it will be faster than "expanding the whole list" which is the way taking the longest time of tackling this problem.

Here is an explanation: https://stackoverflow.com/a/1761646/129202

And I quote the general way of doing it in three steps:

1. calculate the sum of all the weights

2. pick a random number that is 0 or greater and is less than the sum of the weights

3. go through the items one at a time, subtracting their weight from your random number, until you get the item where the random number is less than that item's weight

Answer 4

Here is the simple method:

private static string GenerateStatus()
    {
        var validStatuses = new Dictionary<char, string> 
        {
            {'1', "InProcess"}, {'2',"Partial"}, {'3', "Failed"}, {'4', "Delivered"}, {'5',  "NTD"}, {'6',  "Filtered"}, {'7',  "Rejected"}, {'8',  "Waiting"}, {'9',  "Retrying"}, {'A', 
            "Suspended"}, {'B',  "Complete"}
        };
        const string statusDistribution = "4441444444344444A414444444434444447444B41444414444444444444544444441444444444344444A4444484144444446444449444441444444";

        return validStatuses[statusDistribution[_rand.Next(0, statusDistribution.Length)]];
    }

The idea is simple. Use as many indices (as '3') as you want weight has to be. 40 for '4' and only 1 for '2', for example.