Why am I getting duplicates?

Question

I've built a Keno game, and it picks 20 random numbers out of an arraylist, NumbersToPickFrom. I generate a random number and then check if that number is currently in the numbers available to pick from. If it is, I add it to my arraylist of numbers that will be used as the lottery numbers, randomPicks, and then I remove it from the available numbers. If it's not in the list, that means it's already been picked, and I need a new number. I use a goto to start over. I thought it was working fine, but it seems I've been getting duplicates. Am I using the ArrayList.Remove function wrong? If it's removed, I shouldn't be getting duplicates in my final listing of random picks. If anybody can see where I missed something, that would be helpful. The below code is just the code involved in what I'm talking about.

private void GeneratePicks()
    {
        for (int i = 1; i <= 20; )
        {
        Retry:
            int rInt = GenerateRandomPick();
            if (NumbersToPickFrom.Contains(rInt))
            {
                RandomPicks.Add(rInt);

                NumbersToPickFrom.Remove(rInt);
                i++;
                //PickBox.Text += rInt + " ,";
                RandomPicks.Sort();
            }
            else
            {
                goto Retry;
            }
        }

    }

    private int GenerateRandomPick()
    {
        int rInt = rand.Next(1,81);
        return rInt;
    }

    private void initializeArray()
    {
        for (int i = 1; i <= 80; i++)
        {
            NumbersToPickFrom.Add(i);
        }
    }

Answer 1

I found that your code is working fine.

I added the following public variables to make it work though (on my machine)

   List<int> NumbersToPickFrom = new List<int>();
   List<int> RandomPicks = new List<int>();
   Random rand = new Random();

Though on the second run, i found that the number of items in RandomPicks have doubled and there were duplicates as well, so I changed initializeArray() as below

   private void initializeArray()
   {
       for (int i = 1; i <= 80; i++)
       {
           NumbersToPickFrom.Add(i);
       }

       RandomPicks.Clear();    // Added this to clear the existing values in the list.
   }

Answer 2

I ran your code and didn't get any duplicates at all.

Nevertheless, the approach of repeatedly picking random numbers and comparing to the shrinking list isn't the best way to do this.

Try this instead:

RandomPicks =
    Enumerable
        .Range(1, 80)
        .OrderBy(n => rand.Next())
        .Take(20)
        .OrderBy(n => n)
        .ToList();

Answer 3

If you want to do it "old school" and actually watch what's happening, change your GeneratePicks() method to this:

private void GeneratePicks()
{
    RandomPicks = new List<int>();
    initializeArray();
    for (int i = 0; i < 20; ++i)
    {
        int randomIndex = rand.Next(1, 80 - i);
        int randomPick = NumbersToPickFrom[randomIndex];
        RandomPicks.Add(randomPick);
        NumbersToPickFrom[randomIndex] = NumbersToPickFrom[80 - i - 1];
    }
    RandomPicks.Sort();
}

This will run through exactly 20 times and guarantee non-duplicates.

Answer 4

I can't see any error in your code, and tested your code by running it 100000 times and didn't get any duplicates.

There are however better methods for getting random numbers. One easy improvement would be to randomly pick a number from the NumbersToPickFrom list instead of just picking a number, then you don't need the inner loop.

There is a nicer way to pick lottery numbers. You can loop through the numbers and calculate the probability that each number should be picked. The probability of a number being picked is PicksLeft / NumbersLeft, for example the probability for the number 1 to be picked is 20 / 80, and then the probability changes depending on which numbers are picked:

private void GeneratePicks() {
  int pick = 20;
  for (int n = 1; pick > 0; n++) {
    if (rand.Next(81 - n) < pick) {
      RandomPicks.Add(n);
      pick--;
    }
  }
}

As the numbers are picked in order, you don't even have to sort the numbers afterwards, and you don't need the NumbersToPickFrom list.