0
$\begingroup$

How many random integers from (1-n) must I produce to get all n integers
Assume a perfect random
Because of duplicates it will be more than n

I understand there will be variance but is there an upper bound?

From this program it is about (5 to 6) * n random to get n unique

It is same as the dice question. If I have an n sided dice how many rolls to get all n.

private static int Guesses()
{
    Random rand = new Random();
    int sample = 100;
    int sum = 0;
    HashSet<int> hs = new HashSet<int>();
    for (int j = 0; j < sample * sample; j++)
    {
        hs.Clear();
        do
        {
            hs.Add(rand.Next(sample));
            sum++;
        }  while (hs.Count < sample);
    }
    Debug.WriteLine(sum / sample / sample);
    return (sum / sample / sample / sample);
}
$\endgroup$
  • 1
    $\begingroup$ N unique what? Your question is unclear. $\endgroup$ – Tim Jul 19 '17 at 18:43
  • 1
    $\begingroup$ stats.stackexchange.com/questions/48396/… $\endgroup$ – Sycorax Jul 19 '17 at 18:51
  • $\begingroup$ @Tim integer - I will up date the question $\endgroup$ – paparazzo Jul 19 '17 at 19:30
  • $\begingroup$ @Sycorax Yes it is duplicate. I flagged it. $\endgroup$ – paparazzo Jul 19 '17 at 19:33
  • $\begingroup$ "From this program it is about (5 to 6) * n random to get n unique." Hmm, if n = 1, then (5 to 6) * 1 are not needed. 1 will suffice. Basing your rule of thumb on one particular value of n (100) is not a good way of getting a rule valid for general n. $\endgroup$ – Mark L. Stone Jul 19 '17 at 19:37