开发者

how to use Linq to generate unique random number

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).Se开发者_开发知识库lect(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


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.


In functional programming it is usual to create infinite sequences. It might sound a little bizarre at first but it can be very usefull at some situations. Supose you have an extention as such:

public static class EnumerableExtentions
{
    public static IEnumerable<T> Infinite<T>(Func<int, T> generator)
    {
        int count = 0;
        checked {
            while (true)
                yield return generator(count++);
        }
    }
}

I can use it to create infinite sequences like:

var oddNumbers = EnumerableExtentions.Infinite(n => 2*n + 1)

That is an infinite sequence of all odd numbers. I could take only the first 10, for example:

oddNumbers.Take(10);

would yield:

1 3 5 7 9 11 13 15 17 19

Because of the defered execution, we don´t get a StackOverflowException (you gotta be carefull though).

The same principle can be used to create an infinite random sequence, distinct it and then taking the first 10:

var r = new Random();
var randomNumbers = EnumerableExtentions
                    .Infinite(i=> r.Next (0, 20))
                    .Distinct()
                    .Take(10);

If you need, you can make an OrderBy(s=>s) at the end.


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.


Why not do:

Enumerable.Range(0, 20)
          .OrderBy(x => Guid.NewGuid().GetHashCode())
          .Distinct()
          .Take(10)
          .ToArray();


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.


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));
    }
}


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


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();
        }
    }
}


Why not order by a random? like this

var rnd = new Random();
var randomSeq = Enumerable.Range(1,20).OrderBy(r => rnd.NextDouble()).Take(10).ToList();


Can you do something like this?

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

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜