how to use Linq to generate unique random number

Question

Hi there, here is my Linq code to generate a list of random numbers which contains 10 numbers ranging from 0 to 20

Random rand = new Random();
var randomSeq = Enumerable.Repeat(0, 10).Select(i => rand.Next(0,20));

Result:

6

19

18

7

18

12

12

9

2

18

as you can see i have three 18s and two 12s..

I have tried to use Distinct() function, but it will not fill up the list (e.g only fill up 8 out of 10 numbers) Question: How can I generate unique number (i.e non repeatable numbers ) Many thanks

Answer 1

store the generated result in an array, so anytime you generate e new number check if it has been generated before, if yes generate another one, otherwise take the number and save it in the array

Answer 2

Unless there is an absolute requirement to use LINQ, I'd suggest that you do something like this...

Answer 3

You want to generate a random permutation of the numbers 0 to 19 and pick 10 of these numbers. The standard algorithm for generating a random permutation is Fisher-Yates shuffle. After generating a random permutation you can just pick the first 10 numbers.

It is not to hard to come up with an ad-hoc algorithm like repeatedly choosing a new number if a collision occured but they usually fail to have good statistical properties, have nondeterministic runtime or don't even guarantee termination in the worst case.

Note that this solution is no good choice if the numbers are of different order. Generating a permuation of the numbers below a million only to pick ten is not the smartest thing one can do.

UPDATE

I just realized that you can just stop the algorithm after generating the first ten elements of the permutation - there is no need to build the whole permutation.

Answer 4

Just create a list of sequential valid numbers. Then generate a random index from this list and return (and remove from list) the number at the index.

static class Excensions
{
    public static T PopAt<T>(this List<T> list, int index)
    {
        T ret = list[index];
        list.RemoveAt(index);
        return ret;
    }
}

class Program
{
    static void Main()
    {
        Random rng = new Random();
        int length = 10; //sequence length
        int limit = 20; //maximum value
        var avail = Enumerable.Range(0, limit).ToList();
        var seq = from i in Enumerable.Range(0, length)
                  select avail.PopAt(rng.Next(avail.Count));
    }
}

Answer 5

Can you do something like this?

Random rand = new Random();
var randomSeq = Enumerable.Range(0, 20).OrderBy(i => rand.Next(0,20)).Take(10);

Answer 6

How about using a utility enumerable method:

    static IEnumerable<int> RandomNumbersBetween(int min, int max) 
    {
        int availableNumbers = (max - min) + 1 ;
        int yieldedNumbers = 0;

        Random rand = new Random();
        Dictionary<int, object> used = new Dictionary<int, object>();

        while (true)
        {
            int n = rand.Next(min, max+1); //Random.Next max value is exclusive, so add one
            if (!used.ContainsKey(n))
            {
                yield return n;
                used.Add(n, null);

                if (++yieldedNumbers == availableNumbers)
                    yield break;
            }
        }
    }

Because it returns IEnumerable, you can use it with LINQ and IEnumerable extension methods:

RandomNumbersBetween(0, 20).Take(10)

Or maybe take odd numbers only:

RandomNumbersBetween(1, 1000).Where(i => i%2 == 1).Take(100)

Et cetera.

Edit:

Note that this solution has terrible performance characteristics if you are trying to generate a full set of random numbers between min and max.

However it works efficiently if you want to generate, say 10 random numbers between 0 and 20, or even better, between 0 and 1000.

In worst-case scenario it can also take (max - min) space.

Answer 7

At LINQ exchange, they discuss a method of randomly reordering a list with LINQ and give a code example which will generate a random permutation of the numbers you want.

They say (paraphrasing, and adapted for this problem):

Randomly Sort a List Array With LINQ OrderBy

// create and populate the original list with 20 elements
   List<int> MyList = new List<int>(20);
   for (int i = 0; i < 20; i++)
   MyList.Add(i);
// use System.GUID to generate a new GUID for each item in the list
   List<int> RandomList = MyList.OrderBy(x => System.Guid.NewGuid()).ToList();

LINQ OrderBy will then sort the array by the list of GUID's returned.

Now you can just take the first 10 elements of the list, and you've got your solution.

They note that using the System.Guid.NewGuid() yields the same distribution spread as the Fisher-Yates shuffle algorithm, and this way you won't have to actually implement the algorithm yourself.

Answer 8

Using a custom RepeatUntil extension and relying on closures:

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    public static class CoolExtensions
    {
        public static IEnumerable<TResult> RepeatUntil<TResult>( TResult element, Func<bool> condition )
        {
            while (!condition())
                yield return element;
        }
    }

    class Program
    {
        static void Main( string[] args )
        {
            Random rand = new Random();
            HashSet<int> numbers = new HashSet<int>();

            var randomSeq = CoolExtensions.RepeatUntil( 0, () => numbers.Count >= 10).Select( i => rand.Next( 0, 20 ) ).Select( x => numbers.Add(x));

            // just used to evaluate the sequence
            randomSeq.ToList();

            foreach (int number in numbers)
                Console.WriteLine( number );

            Console.ReadLine();
        }
    }
}