locked
How can I generate 3 random integers that are not the same? RRS feed

  • Question

  • for example, so far I have

     

     

                int a;
                int b;
                int c;
                
                int count = 0;
    
                Random rand = new Random();
    
    
                do
                {
                    
                    a = rand.Next(1, 20);
                    b = rand.Next(1, 20);
                    c = rand.Next(1, 20);
                    
    
                     
    
                } while (true);
                Console.ReadLine();


    I need to make sure that on every pass there is no chance that a b or c will equal eachother.

     

    I know chances are small as it is, but I need to make sure that by some coincidence they are not the same, for example, I want to make sure that in no way b=c, or a=c, or b=a, etc.

     

    Any advice?

     

    Thursday, October 13, 2011 1:32 AM

Answers

  • Hi,

    How about do it through Linq?

    var sequence = Enumerable.Range( 1 , 20 ).OrderBy( n => n * n * ( new Random() ).Next() );
    
    var result = sequence.Distinct().Take( 3 );
    

    It takes only two lines.

    (Reference to this link: Generating random sequences with LINQ)

     

    Hope this information is helpful to you.


    Ouch Liu
    Welcome to visit by blog: Ouch@點部落
    Welcome to join the Designer x Developer group on Facebook: Facebook 設計x程式 社團
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:44 AM
    Thursday, October 13, 2011 1:49 AM
  • Simple but inefficient, and doesn't scale well to more integers:

                do
                {
                    a = rand.Next(1, 20);
                    b = rand.Next(1, 20);
                    c = rand.Next(1, 20);
                } while ((a==b)||(b==c)||(a==c));

     

    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:44 AM
    Thursday, October 13, 2011 8:15 AM
  • Actually that was rubbish code I posted before, here's a class.

        class MyRandom
        {
            List<int> available;
            Random rand = new Random();

            public MyRandom(int max)
            {
                this.available = Enumerable.Range(1, max).ToList();
            }

            public MyRandom(int min, int max)
            {
                this.available = Enumerable.Range(min, max).ToList();
            }

            public int Count()
            {
                return available.Count;
            }

            public int Next()
            {
                if (available.Count == 0)
                    throw new Exception();

                int index = rand.Next(1, available.Count());

                int value = this.available[index];
                this.available.RemoveAt(index);

                return value;
            }

        }

     

    Use it like this...

                MyRandom rand = new MyRandom(1, 20);
                int a = rand.Next();
                int b = rand.Next();
                int c = rand.Next();

     

    Much better apart from calling it MyRandom but ...

     

     

     


    "The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination." - Fred Brooks
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:45 AM
    Thursday, October 13, 2011 10:39 AM
  • Use the random selection from an array approach that was described by Ante.

     

                List<int> available = Enumerable.Range(1, 20).ToList();

                Random rand = new Random();
                int index;
               
                index = rand.Next(1, available.Count());

                int a = available[index];
                available.RemoveAt(index);


                index = rand.Next(1, available.Count());

                int b = available[index];
                available.RemoveAt(index);


                index = rand.Next(1, available.Count());


                int c = available[index];
                available.RemoveAt(index);


    "The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination." - Fred Brooks
    • Edited by Derek Smyth Thursday, October 13, 2011 10:31 AM
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:45 AM
    Thursday, October 13, 2011 10:31 AM
  • If you want to avoid duplicates, you'll have to test whether the newly generated number is not in the list of the previously generated

    			Random rnd = new Random();
    
    
    			int itemsNeeded = 3;
    
    			List<int> numbers = new List<int>(itemsNeeded);
    			int n;
    
    			do {
    				n = rnd.Next(1, 20);
    				if (!numbers.Contains(n))
    				{
    					numbers.Add(n);
    				}
    
    			} while (numbers.Count < itemsNeeded);
    
    
    
    			for (int i = 0; i < numbers.Count; i++)
    				Console.WriteLine(numbers[i]);
    			Console.ReadLine();
    

     

    • Proposed as answer by CountryStyle Friday, October 14, 2011 12:05 PM
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:45 AM
    Thursday, October 13, 2011 10:36 AM
  • Use the random selection from an array approach that was described by Ante.

    Here is a variant of your MyRandom class storing ranges of available numbers.

    class MyRandom
    {
        struct Range
        {
            public int min, size;
            public override string ToString()
            {
                return min + "-" + (min + size - 1);
            }
        }
        List<Range> available;
        int count;
        Random rand = new Random();
    
        public MyRandom(int max)
        {
            this.available = new List<Range> { new Range { min = 1, size = count = max } };
        }
    
        public MyRandom(int min, int max)
        {
            this.available = new List<Range> { new Range { min = min, size = count = max - min + 1 } };
        }
    
        public int Count()
        {
            return count;
        }
    
        public int Next()
        {
            lock (available)
            {
                if (count == 0)
                    throw new InvalidOperationException();
    
                int index = rand.Next(1, count);
    
                for (int i = 0; i < available.Count; i++)
                {
                    Range range = available[i];
                    if (index < range.size)
                    {
                        int value = range.min + index;
                        available.RemoveAt(i);
                        if (index > 0)
                            available.Add(new Range { min = range.min, size = index });
                        if (index < range.size - 1)
                            available.Add(new Range { min = value + 1, size = range.size - index - 1 });
                        return value;
                    }
                    else
                    {
                        index -= range.size;
                    }
                }
            }
    
            // Should never reach this statement
            throw new InvalidOperationException();
        }
    }
    
    • Edited by Louis.fr Thursday, October 13, 2011 12:30 PM
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:46 AM
    Thursday, October 13, 2011 12:29 PM
  • One more option:

     

                Random r = new Random();
                List<int> numbers = new List<int>();
                for (int i = 0; i < 3; i++)
                {
                    while (true)
                    {
                        int tempNum = r.Next(1, 5);
                        if (!numbers.Contains(tempNum))
                        {
                            numbers.Add(tempNum);
                            break;
                        }
                    }
                }
    
                //now you have 3 numbers in the list<T>.
    



    Mitja
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:46 AM
    Thursday, October 13, 2011 2:48 PM
  •  
    var res = Random(3, 1, 20);
    System.Diagnostics.Trace.WriteLine(string.Join("; ", res));
    ...
    public IEnumerable<int> Random(int count, int min, int max)
    {
        var set = new HashSet<int>();
        var rnd = new Random();
        while (set.Count != count)
        {
            var v = rnd.Next(min, max);
            if (set.Contains(v) == false)
            {
                yield return v;
                set.Add(v);
            }
        }
    }
    


    MSDN: "The HashSet(Of T) class provides high-performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order."

    • Edited by Malobukv Thursday, October 13, 2011 3:01 PM
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:47 AM
    Thursday, October 13, 2011 2:55 PM
  • using System;
    using System.Collections.Generic;
    using System.Text;
    
    namespace SharxXTestConsole
    {
        //
        // Program
        //
        class Program
        {
            private static Randomizer randomizer = new Randomizer();
    
            static void Main(string[] args)
            {
                Console.WriteLine("Test 1: Generate 3 unique random numbers");
                Console.ReadKey();
    
                int A = randomizer.Next(1, 30);
                int B = randomizer.Next(1, 30);
                int C = randomizer.Next(1, 30);
    
                Console.WriteLine(A);
                Console.WriteLine(B);
                Console.WriteLine(C);
                Console.ReadKey();
    
                Console.WriteLine("Test 2: Generate 20 unique random numbers");
                Console.ReadKey();
                randomizer.Reset();
                for (int i = 0; i < 20; i++)
                {
                    Console.WriteLine(randomizer.Next(1,100));
                }
                Console.ReadKey();
            }
        }
    
        //
        // Randomizer
        //
        public class Randomizer : Random
        {
            List<int> returnedNumbers = new List<int>();
    
            public void Reset()
            {
                returnedNumbers.Clear();
            }
    
            private bool IsUnique(int number)
            {
                lock (returnedNumbers)
                {
                    if (returnedNumbers.Contains(number))
                    {
                        return false;
                    }
                    else
                    {
                        returnedNumbers.Add(number);
                        return true;
                    }
                }
            }
        
            public override int Next()
            {
                int number = base.Next();
                while (!IsUnique(number))
                {
                    number = base.Next();
                }
                return number;
            }
    
            public override int Next(int maxValue)
            {
                int number = base.Next(maxValue);
    
                while (!IsUnique(number))
                {
                    number = base.Next();
                }
                return number;
            }
    
            public override int Next(int minValue, int maxValue)
            {
                int number = base.Next(minValue, maxValue);
                while (!IsUnique(number))
                {
                    number = base.Next(minValue, maxValue);
                }
                return number;
            }
        }
    }
    
    

    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:43 AM
    Friday, October 14, 2011 11:17 PM
  • Yes, and all of those examples are completely awful if you're choosing a large number of numbers from a large range of numbers.
    Like what I've said, different scenarios have different solution :)
    I don't think there's a general solution that fits every scenario.

    Here's a code (extracted from a simulation game we'd developed last year, uses the shuffle array technique) that draw 255 unique values from a large range (uint.MaxValue):

    var r = new Random();
    var s = Enumerable.Range(0x00, 0xff);
    
    // shuffle a large set of int.MaxValue
    var hh = s.OrderBy(x => r.Next()).ToArray();
    var hl = s.OrderBy(x => r.Next()).ToArray();
    var lh = s.OrderBy(x => r.Next()).ToArray();
    var ll = s.OrderBy(x => r.Next()).ToArray();
    
    // Draw 255 unique unsigned integers from 0 to uint.MaxValue
    var ints = new uint[255];
    for (var i = 0; i < 255; i++)
    	ints[i] = (uint)(hh[i] << 24 | hl[i] << 16 | lh[i] << 8 | ll[i]);
    
    // Print them
    for (var i = 0; i < 255; i++)
    	Console.WriteLine(ints[i]);
    

     If you want to draw larger than 255, then instead of bytes make then array of words.

    Mark the best replies as Answers! | Blog: http://devpinoy.org/blogs/cvega
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:43 AM
    Wednesday, October 19, 2011 5:49 AM

All replies

  • Hi,

    How about do it through Linq?

    var sequence = Enumerable.Range( 1 , 20 ).OrderBy( n => n * n * ( new Random() ).Next() );
    
    var result = sequence.Distinct().Take( 3 );
    

    It takes only two lines.

    (Reference to this link: Generating random sequences with LINQ)

     

    Hope this information is helpful to you.


    Ouch Liu
    Welcome to visit by blog: Ouch@點部落
    Welcome to join the Designer x Developer group on Facebook: Facebook 設計x程式 社團
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:44 AM
    Thursday, October 13, 2011 1:49 AM
  • I want to stay away from LINQ for now, just getting my feet wet in c sharp is enough at the moment.
    Thursday, October 13, 2011 2:06 AM
  • This awkward and verbose, but it might do the job.

    Set up a list of the numbers from 1 to 20.

    Get a random number from 1 to 20, call it i. Set a = i;

    Remove the ith number from the list.

    Get a random number from 1 to 19, call it j. Set b = the jth number in the list.

    Remove the jth number from the list.

    Get a random number from 1 to 18, call it k. Set c = the kth number in the list.
    Thursday, October 13, 2011 2:31 AM
  • yeah there is very small possibility that random number may repeat so i suggest you to try to generate three different random number of same length very much like generating capcta code.... Once you have this code then you can concate a idetifier number to your random no

    e.g
    Suppose you get three different number of length of 5 
    a = 45623
    b = 98756
    c = 45896

    now concate identifier to your random number 

    a =  a + "1";
    b = b + "2" ;
    c = c + "3" 

    Note you need to concate not add identifier 

    Hope this might help you 


    Sumit Kumar
    Thursday, October 13, 2011 4:30 AM
  • a = rand.Next(1, 20);
    b = rand.Next(1, 19);
    if (b == a) b=20;
    c = rand.Next(1, 18);
    if (c == a)
        c = 19;
    else if (c == b)
        c = 20;
    

    • Proposed as answer by Wyck Friday, October 14, 2011 3:35 AM
    • Unproposed as answer by Wyck Friday, October 14, 2011 12:05 PM
    Thursday, October 13, 2011 7:30 AM
  • Simple but inefficient, and doesn't scale well to more integers:

                do
                {
                    a = rand.Next(1, 20);
                    b = rand.Next(1, 20);
                    c = rand.Next(1, 20);
                } while ((a==b)||(b==c)||(a==c));

     

    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:44 AM
    Thursday, October 13, 2011 8:15 AM
  • The only problem with Matthew's solution is that it's theoretically possible for the while loop to never end. The best solution should have a definite end point.
    Thursday, October 13, 2011 9:13 AM
  • There are two distinct solutions proposed.  One selects an integer from a range and removes the integer.  The other selects an integer from a range and then replaces the integer.  In the first, duplicates are not possible and is called selection without replacement.  In the second, duplicates are possible, but if a duplicate occurs selections continue until there are no duplicates.  The statistics of the two methods are quite different.  The second method is not usually found in actual situations.
    Thursday, October 13, 2011 9:27 AM
  • Third solution, shuffle an array :)


    var range = Enumerable.Range(0, 21).ToArray();
    var count = range.Length;
    var rnd = new Random();
    
    // shuffle our array
    for (int i = count - 1; i > 0; i--) {
    	int x = rnd.Next(0, count);
    	int t = range[x];
    	range[x] = range[i];
    	range[i] = t;
    }
    
    // Since it was shuffled, the first 3 will be guaranteed unique :D
    int a = range[0];
    int b = range[1];
    int c = range[2];
    
    Console.WriteLine("a = {0}", a);
    Console.WriteLine("b = {0}", b);
    Console.WriteLine("c = {0}", c);
    


    Mark the best replies as Answers! | Blog: http://devpinoy.org/blogs/cvega
    Thursday, October 13, 2011 9:55 AM
  • Simple but inefficient

    Too quickly thought and written. My code can actually produce duplicates.
    Thursday, October 13, 2011 10:08 AM
  • Use the random selection from an array approach that was described by Ante.

     

                List<int> available = Enumerable.Range(1, 20).ToList();

                Random rand = new Random();
                int index;
               
                index = rand.Next(1, available.Count());

                int a = available[index];
                available.RemoveAt(index);


                index = rand.Next(1, available.Count());

                int b = available[index];
                available.RemoveAt(index);


                index = rand.Next(1, available.Count());


                int c = available[index];
                available.RemoveAt(index);


    "The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination." - Fred Brooks
    • Edited by Derek Smyth Thursday, October 13, 2011 10:31 AM
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:45 AM
    Thursday, October 13, 2011 10:31 AM
  • If you want to avoid duplicates, you'll have to test whether the newly generated number is not in the list of the previously generated

    			Random rnd = new Random();
    
    
    			int itemsNeeded = 3;
    
    			List<int> numbers = new List<int>(itemsNeeded);
    			int n;
    
    			do {
    				n = rnd.Next(1, 20);
    				if (!numbers.Contains(n))
    				{
    					numbers.Add(n);
    				}
    
    			} while (numbers.Count < itemsNeeded);
    
    
    
    			for (int i = 0; i < numbers.Count; i++)
    				Console.WriteLine(numbers[i]);
    			Console.ReadLine();
    

     

    • Proposed as answer by CountryStyle Friday, October 14, 2011 12:05 PM
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:45 AM
    Thursday, October 13, 2011 10:36 AM
  • Actually that was rubbish code I posted before, here's a class.

        class MyRandom
        {
            List<int> available;
            Random rand = new Random();

            public MyRandom(int max)
            {
                this.available = Enumerable.Range(1, max).ToList();
            }

            public MyRandom(int min, int max)
            {
                this.available = Enumerable.Range(min, max).ToList();
            }

            public int Count()
            {
                return available.Count;
            }

            public int Next()
            {
                if (available.Count == 0)
                    throw new Exception();

                int index = rand.Next(1, available.Count());

                int value = this.available[index];
                this.available.RemoveAt(index);

                return value;
            }

        }

     

    Use it like this...

                MyRandom rand = new MyRandom(1, 20);
                int a = rand.Next();
                int b = rand.Next();
                int c = rand.Next();

     

    Much better apart from calling it MyRandom but ...

     

     

     


    "The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination." - Fred Brooks
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:45 AM
    Thursday, October 13, 2011 10:39 AM
  • Simple but inefficient

    Too quickly thought and written. My code can actually produce duplicates.
    Ah, I was referring to the code sample I wrote, not yours. :)
    Thursday, October 13, 2011 11:02 AM
  • Here's an O(N) solution:

     

    using System;
    using System.Collections.Generic;
    
    namespace Demo
    {
        class Program
        {
            static void Main(string[] args)
            {
                Random rng = new Random();
    
                foreach (int number in RandomlySelectedNumbers(3, 1, 20, rng))
                {
                    Console.WriteLine(number);
                }
            }
    
            /// <summary>
            /// Randomly selects <paramref name="count"/> numbers with values
            /// between <paramref name="minimum"/> and <paramref name="maximum"/> inclusive.
            /// </summary>
            /// <param name="count">The count of values to select.</param>
            /// <param name="minimum">The minimum value to select.</param>
            /// <param name="maximum">The maximum value to select.</param>
            /// <param name="rng">The random number generator to use.</param>
            /// <returns>A sequence of the randomly-selected numbers.</returns>
            /// <remarks>This is an O(N) algorithm (N is the range of values to generate).</remarks>
    
            public static IEnumerable<int> RandomlySelectedNumbers(int count, int minimum, int maximum, Random rng)
            {
                if (rng == null)
                {
                    throw new ArgumentNullException("rng");
                }
    
                if (count < 0 || count > (maximum-minimum+1))
                {
                    throw new ArgumentOutOfRangeException("count", count, "count must be between 0 and (maximum-minimum+1)");
                }
    
                maximum = maximum - minimum + 1;
    int available = maximum; int remaining = count; for (int current = 0; current < maximum; ++current) { if (rng.NextDouble() < remaining/(double)available) { yield return current + minimum; --remaining; } --available; } } } }


     




    • Edited by Matthew Watson Thursday, October 13, 2011 11:35 AM
    • Proposed as answer by servy42 Thursday, October 13, 2011 2:57 PM
    • Unproposed as answer by servy42 Thursday, October 13, 2011 2:58 PM
    Thursday, October 13, 2011 11:14 AM
  • If the range of available numbers is very big, it could be more efficient storing ranges of available numbers instead.

    Thursday, October 13, 2011 12:09 PM
  • Here's an O(N) solution

    Not counting the randomizing of the result if you don't want to have the numbers sorted.
    Thursday, October 13, 2011 12:10 PM
  • Use the random selection from an array approach that was described by Ante.

    Here is a variant of your MyRandom class storing ranges of available numbers.

    class MyRandom
    {
        struct Range
        {
            public int min, size;
            public override string ToString()
            {
                return min + "-" + (min + size - 1);
            }
        }
        List<Range> available;
        int count;
        Random rand = new Random();
    
        public MyRandom(int max)
        {
            this.available = new List<Range> { new Range { min = 1, size = count = max } };
        }
    
        public MyRandom(int min, int max)
        {
            this.available = new List<Range> { new Range { min = min, size = count = max - min + 1 } };
        }
    
        public int Count()
        {
            return count;
        }
    
        public int Next()
        {
            lock (available)
            {
                if (count == 0)
                    throw new InvalidOperationException();
    
                int index = rand.Next(1, count);
    
                for (int i = 0; i < available.Count; i++)
                {
                    Range range = available[i];
                    if (index < range.size)
                    {
                        int value = range.min + index;
                        available.RemoveAt(i);
                        if (index > 0)
                            available.Add(new Range { min = range.min, size = index });
                        if (index < range.size - 1)
                            available.Add(new Range { min = value + 1, size = range.size - index - 1 });
                        return value;
                    }
                    else
                    {
                        index -= range.size;
                    }
                }
            }
    
            // Should never reach this statement
            throw new InvalidOperationException();
        }
    }
    
    • Edited by Louis.fr Thursday, October 13, 2011 12:30 PM
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:46 AM
    Thursday, October 13, 2011 12:29 PM
  • I'm sorting through the answers guys. Thanks for all the replies.

    :(

    Thursday, October 13, 2011 2:29 PM
  • One more option:

     

                Random r = new Random();
                List<int> numbers = new List<int>();
                for (int i = 0; i < 3; i++)
                {
                    while (true)
                    {
                        int tempNum = r.Next(1, 5);
                        if (!numbers.Contains(tempNum))
                        {
                            numbers.Add(tempNum);
                            break;
                        }
                    }
                }
    
                //now you have 3 numbers in the list<T>.
    



    Mitja
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:46 AM
    Thursday, October 13, 2011 2:48 PM
  •  
    var res = Random(3, 1, 20);
    System.Diagnostics.Trace.WriteLine(string.Join("; ", res));
    ...
    public IEnumerable<int> Random(int count, int min, int max)
    {
        var set = new HashSet<int>();
        var rnd = new Random();
        while (set.Count != count)
        {
            var v = rnd.Next(min, max);
            if (set.Contains(v) == false)
            {
                yield return v;
                set.Add(v);
            }
        }
    }
    


    MSDN: "The HashSet(Of T) class provides high-performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order."

    • Edited by Malobukv Thursday, October 13, 2011 3:01 PM
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:47 AM
    Thursday, October 13, 2011 2:55 PM
  • For all of the ones that just do a "pick a random number, and if I haven't already picked it add it to the list", which is about half here, they're easy, but not a good idea.  They are all O(infinity) solutions....
    Thursday, October 13, 2011 3:00 PM
  • [STAThread]
    static void Main()
    {
        int num1 = Random(1, 20);
        int num2 = Random(1, 20);
        int num3 = Random(1, 20);
    }
    
    static Random random = new Random();
    public static int Random(int min, int max)
    {
        int rand = random.Next(min, int.MaxValue);
    
        rand = rand % max + 1;
    
        return rand;
    }


    Thursday, October 13, 2011 3:17 PM
  • Hey Louis.fr, so I decided not to like this line of code in your example

    this.available = new List<Range> { new Range { min = min, size = count = max - min + 1 } };

    because of the side effect of setting count in the creation of Range... so I decided to write it better. Little did I realise how tricky it would be creating the new ranges based on the generated random value.

    For example

    The range is set [1-20] and the first number was 2 then that would mean two ranges [1-1] and [3-20]. Imagine the next number selected was 1, well that would mean the range [1-1] is deleted, or more accurately no new range is added, and only [3-20] would remain.

    Then what happens if it occurs at the higher end.... 19 then 20 ... and then what if the range was 15-20 and 20 was selected.... and so on.

    So just because I didn't like that one line of code I ended up basically reimplementing the whole thing and I should have left 30 minutes ago.

    Anyway this is not a competition... not interested in code being better than other code but I wrote this thing so I'll post it. It's interesting to see how different developers code the same solution a different way... this hasn't been fully tested but just out of interest here's your idea of ranges filtered through my brain.  :)  Wish I hadn't bothered. :)

     

    I decided to stick with max and min and to calculate the size and the count.

    Anyway take it easy, time to go!

     

        class MyRandom
        {
            struct Range
            {
                public int min, max;

                public int Size()
                {
                    return (max - min) + 1;
                }

                public override string ToString()
                {
                    return min + "-" + max;
                }
            }

            List<Range> ranges;
            Random rand = new Random();

            public MyRandom(int max)
            {
                this.ranges = new List<Range> { new Range { min = 1, max = max } };
            }

            public MyRandom(int min, int max)
            {
                this.ranges = new List<Range> { new Range { min = min, max = max } };
            }

            public int Count()
            {
                return ranges.Sum(rng => rng.Size());
            }

            public int Next()
            {
                lock (ranges)
                {
                    if (this.Count() == 0)
                        throw new InvalidOperationException();

                    // select a random range
                    int rndRangeIndex = rand.Next(1, this.ranges.Count) - 1;
                    Range range = ranges[rndRangeIndex];

                    // use that range to produce a random number
                    int value = rand.Next(range.min, range.max);

                    ranges.RemoveAt(rndRangeIndex);
                    if (range.min == value) {
                        this.AddRange(range.min + 1, range.max);
                    }
                    else if (range.max == value) {
                        this.AddRange(range.min, range.max - 1);
                    }
                    else {
                        this.AddRange(range.min, value - 1);
                        this.AddRange(value + 1, range.max);
                    }

                    return value;
                }
            }

            public void AddRange(int min, int max)
            {
                Range rng = new Range { min = min, max = max };
                if (rng.Size() > 0)
                    ranges.Add(rng);
            }
        }

     

     

     

     

     


    "The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination." - Fred Brooks
    • Edited by Derek Smyth Thursday, October 13, 2011 3:42 PM
    Thursday, October 13, 2011 3:41 PM
  • Derek, I like your solution, a lot, so don't take this post the wrong way.  The randomness needs a bit of improvement, as right now it's not equally weighted (assuming Random was actually truly random, which I know it's not).

     

    // select a random range
    int rndRangeIndex = rand.Next(1, this.ranges.Count) - 1;
    Range range = ranges[rndRangeIndex];
    
    // use that range to produce a random number
    int value = rand.Next(range.min, range.max);
    


    Looking at this block of code.  Let's assume there are two ranges, 1-1 and 3-20.  We first pick a random range.  We have a 50% chance of picking the first range and a 50% chance of picking the second range, so we'll pick 1 50% of the time, when it only ought to be picked ~5.3% of the time.

    There are a few ways to solve this issue.  The first is to use a weighted random generator to pick the range; this is possible, but probably more work than it needs to be.

    Another would be to pick one number between 0 and one less than this.Count(), let's call it index.  for each group, while the size of that range is less than index, subtract that range's size from the index.  When it is less than the index, pick the item with that index from the range as the one to remove.  (That's how I think of it conceptually, there could potentially be more efficient ways of implementing that in actual code.)

    Thursday, October 13, 2011 4:51 PM
  • I ge the intellectucal exercise of removing the possiblity of a say the #5 being chosen 5 billion times in a row and resulting in an almost never ending loop.

    I did this and the answer and found that Greogory Adams did just about the same thing.  No need to complicate this with shrinking arrays/lists.  Simple code = better code (if the simple code does the job.)  Did not write in the IDE so I hope it is right:

     

    List<int> listInt = new List<int>();
    int foundNumberCount = 0;
    int myRandomNumber;
    Random myRandom = new Random();
    do{
    
    myRandomNumber = myRandom.Next(1,20);
    if(!listInt.Contains(myRandomNumber))
    {
    listInt.Add(myRandomNumber);
    intFoundNumberCount++;
    }
    
    }While(foundNumberCount <3)
    //do what you will without the list
    


    countryStyle


    Friday, October 14, 2011 3:29 AM
  • For all of the ones that just do a "pick a random number, and if I haven't already picked it add it to the list", which is about half here, they're easy, but not a good idea.  They are all O(infinity) solutions....

    It's not true that they are O(infinity) solutions - that would mean that they ALWAYS took an infinite amount of time to run, which clearly is not the case.

    You would have to run the function an infinite amount of times to actually see one of the calls TAKE an infinite amount of time, which sounds somewhat paradoxical I'll admit. ;)

    The actual O(X) will be asymptotic to some value, but I lack the time (and the mathematical skills!) to actually work out the asymptotic value - it's a lot less than infinity, that's for sure. :)



    Friday, October 14, 2011 6:13 AM
  • Just some thoughts, if you select three random numbers and then check if they have occured before and then re-select the non-unique value. Then I would say it's not really random anymore. At least probability theory won't be applicable.

    As others have said, if you are unlucky you will get an infinitive loop, but the probability for this is almost none-existent.

    You could do something like this:

    int tries = 0;
    bool success = false; 

    while(!success && tries != 3)
    {
        tries += 1;
        success = true;

        a = rand.Next(1,20);
        b = rand.Next(1,20);
        c = rand.Next(1,20);

       if ( a == b || a == c || b == c ) success = false;



    if ( !success )
    {
         // Default values
         a = 1;
         b = 5;
         c = 10; 

    This way the loop will end if it succeeded and it will at most not succeed for three times before it ends the loop. This way you can set a/b/c to default numbers (chosen from fair dice rolls.).

    // Filip

    Friday, October 14, 2011 7:22 AM
  • Just some thoughts, if you select three random numbers and then check if they have occured before and then re-select the non-unique value. Then I would say it's not really random anymore. At least probability theory won't be applicable.

    That's not true at all. The chance of any of the remaining numbers being chosen is exactly what it should be.

    Consider the case when you are randomly choosing 3 numbers out of 20.

    For the first random selection, there is a 1 in 20 chance of any of the numbers being chosen.

    For the second random selection there should be a 1 in 19 chance of any of the remaining numbers being chosen. A random number between 1 and 20 is chosen, but if it has already been selected that number is rejected and it is as if it is never selected. Therefore the second random roll has only 19 possible outcomes, each equally likely. This is the correct probability for the selection.

    For the third selection there should be a 1 in 18 chance of any of the remaining numbers being selected. This is the case, even if you repeatedly randomly select a number from 1 to 20 and reject any of the 2 numbers that have already occured: There are only 18 possible outcomes, each equally likely.

     

     

    Friday, October 14, 2011 7:44 AM
  • Just some thoughts, if you select three random numbers and then check if they have occured before and then re-select the non-unique value. Then I would say it's not really random anymore. At least probability theory won't be applicable.

    That's not true at all. The chance of any of the remaining numbers being chosen is exactly what it should be.

    Consider the case when you are randomly choosing 3 numbers out of 20.

    For the first random selection, there is a 1 in 20 chance of any of the numbers being chosen.

    For the second random selection there should be a 1 in 19 chance of any of the remaining numbers being chosen. A random number between 1 and 20 is chosen, but if it has already been selected that number is rejected and it is as if it is never selected. Therefore the second random roll has only 19 possible outcomes, each equally likely. This is the correct probability for the selection.

    For the third selection there should be a 1 in 18 chance of any of the remaining numbers being selected. This is the case, even if you repeatedly randomly select a number from 1 to 20 and reject any of the 2 numbers that have already occured: There are only 18 possible outcomes, each equally likely.

     

     

    Oh yeah, you're right.. My bad!

    You could also do something like this:

     

    List<int> numbers = new List<int> {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    Random random = new Random();
     
    var index = random.Next(0, numbers.Count - 1);
    var a = numbers[index];
    numbers.RemoveAt(index);
     
    index = random.Next(0, numbers.Count - 1);
    var b = numbers[index];
    numbers.RemoveAt(index);
     
    index = random.Next(0, numbers.Count - 1);
    var c = numbers[index];
    numbers.RemoveAt(index);

     

    Might not be optimal if you want to select 3 numbers between 1 and int.MaxValue though.
    Friday, October 14, 2011 7:59 AM
  • :D

    Rest assured that your solution is optimal enough (except that removal of an element in the List will require internal realignment of elements, so I guess swap values is *very-very-slightly* better).

    Here's a variation of my "shuffle list" example I posted above, but limiting to only 'max' number of elements to speed it up:

    var range = Enumerable.Range(0, 20).ToArray();
    var rnd = new Random();
    
    var max = 3;
    var len = range.Length;
    
    for (int i = 0; i < max; i++) {
      var x = rnd.Next(i, len);
      
      // swap
      var t = range[i];
      range[i] = range[x];
      range[x] = t;
    }
    
    // Here, the first 'max' elements of array are guaranteed unique!
    for (var i = 0; i < max; i++)
      Console.WriteLine("element {0} = {1}", i, range[i]);
    



    Mark the best replies as Answers! | Blog: http://devpinoy.org/blogs/cvega
    Friday, October 14, 2011 8:25 AM
  • How can that guarantee that "x" will not be swapped back again?

    Swapping re-arranges the order of elements though, I'd rahter see the value moved to the end of the list, without re-arranging the entire list and without moving anything else into the middle or something like that.

    Could do it with a linked list.... ;)

    Friday, October 14, 2011 8:33 AM
  • Hey Louis.fr, so I decided not to like this line of code in your example

    this.available = new List<Range> { new Range { min = min, size = count = max - min + 1 } };

    because of the side effect of setting count in the creation of Range...


    I set the count here only because I started with min,max then changed it to size, then added the count and was too lazy to move code on another line.

    That line is easily replaced by:

    count = max - min + 1;
    this.available = new List<Range> { new Range { min = min, size = count } };
    


    • Edited by Louis.fr Friday, October 14, 2011 8:38 AM
    Friday, October 14, 2011 8:37 AM
  • Derek, I like your solution, a lot, so don't take this post the wrong way.  The randomness needs a bit of improvement, as right now it's not equally weighted (assuming Random was actually truly random, which I know it's not).

    // select a random range
    int rndRangeIndex = rand.Next(1, this.ranges.Count) - 1;
    Range range = ranges[rndRangeIndex];
    
    // use that range to produce a random number
    int value = rand.Next(range.min, range.max);
    


    Looking at this block of code.  Let's assume there are two ranges, 1-1 and 3-20.  We first pick a random range.  We have a 50% chance of picking the first range and a 50% chance of picking the second range, so we'll pick 1 50% of the time, when it only ought to be picked ~5.3% of the time.

    There are a few ways to solve this issue.  The first is to use a weighted random generator to pick the range; this is possible, but probably more work than it needs to be.

    Another would be to pick one number between 0 and one less than this.Count(), let's call it index.  for each group, while the size of that range is less than index, subtract that range's size from the index.  When it is less than the index, pick the item with that index from the range as the one to remove.  (That's how I think of it conceptually, there could potentially be more efficient ways of implementing that in actual code.)

    An oppertunity to improve code can't be taken the wrong way. Going to just point out that the idea to use ranges was down to Louis.fr ... I just implemented it a bit different because of one line of code I didn't..... and because I was bored as was the major factor as I'm not really in the habit of doing that unless I don't have anything better to do.

    Take the point about the weighting so here is an update with the approach taken. Open to review.Hopefully it will post ok.

    Amazing what you can come up with on a yellow post it note.

     

     

        class RangedRandom
        {
            struct Range
            {
                public int min, max;

                public int Count()
                {
                    return (max - min) + 1;
                }

                public override string ToString()
                {
                    return min + "-" + max;
                }
            }

            List<Range> ranges;
            Random rand = new Random();

            public RangedRandom(int max)
            {
                this.ranges = new List<Range> { new Range { min = 1, max = max } };
            }

            public RangedRandom(int min, int max)
            {
                this.ranges = new List<Range> { new Range { min = min, max = max } };
            }

            public int Count
            {
                get
                {
                    return ranges.Sum(rng => rng.Count());
                }
            }

            public int Next()
            {
                lock (ranges)
                {
                    if (this.Count == 0)
                        throw new InvalidOperationException();

                    // select a random range
                    int rndRangeIndex = WeightedRandomIndex(); // rand.Next(1, this.ranges.Count) - 1;
                    Range range = ranges[rndRangeIndex];


                    // use that range to produce a random number
                    int value = rand.Next(range.min, range.max);
                    ranges.RemoveAt(rndRangeIndex);

                    // if the value in at the minimum boundry then drop the lower boundry number
                    if (range.min == value)
                    {
                        this.AddRange(range.min + 1, range.max);
                    }
                    // if the value in at the maximum boundry then drop the maximum boundry number
                    else if (range.max == value)
                    {
                        this.AddRange(range.min, range.max - 1);
                    }
                    // split the range
                    else
                    {
                        this.AddRange(range.min, value - 1);
                        this.AddRange(value + 1, range.max);
                    }

                    return value;
                }
            }


            /// <summary>
            ///
            /// Ranges (ordered by the count of items in the range):
            ///
            ///     [1-1]       - 1 item
            ///     [19-20]     - 2 items
            ///     [13-17]     - 4 items
            ///     [3-11]      - 9 items
            ///    
            /// Probability that the range should be used
            ///    
            ///     (1.0 / Total Count of Items) * Count of Item in Range
            ///
            ///     [1-1]       -  5.88 %
            ///     [19-20]     - 11.76 %
            ///     [13-17]     - 29.40 %
            ///     [3-11]      - 52.92 %
            ///
            /// This creates a probability weighting like so
            ///
            ///     0.00 
            ///             } Range 0
            ///     0.05
            ///             } Range 1  (0.05 + 0.11)
            ///     0.16
            ///             } Range 2  (0.16 + 0.29)
            ///     0.45
            ///             } Range 3  (0.45 + 0.52) - rounded to 1.0 to complete 100% probability
            ///     1.00
            ///
            /// Random number selected between 0.0 and 1.0, the probability.
            ///
            ///     prob = 0.53
            ///
            ///     0.00 
            ///             } Range 0
            ///     0.05
            ///             } Range 1
            ///     0.16
            ///             } Range 2
            ///     0.45
            /// 0.53 ->     } Range 3 used
            ///     1.00
            ///    
            /// </summary>
            /// <returns></returns>
            private int WeightedRandomIndex()
            {
                // creating weightings for ranges from 0.0 to 1.0
                double accumulator = 0.00;

                List<double> weightings = new List<double>();
                weightings.Add(accumulator);

                for (int i = 0; i < ranges.Count - 1; i++)
                {
                    double weight = (1.0 / this.Count) * ranges[i].Count();
                    weightings.Add(Math.Round(weight + accumulator, 2));

                    accumulator = weight;
                }
                weightings.Add(1.00);


                // produce a random value between 0.0 and 1.0
                // and determine in what ranges weighting it falls in
                double probability = Math.Round(rand.NextDouble(), 2);
                for (int i = 1; i < weightings.Count; i++)
                {
                    // use the weighting to produce the index
                    if (probability >= weightings[i - 1] && probability <= weightings[i])
                    {
                        return i - 1;
                    }
                }
               
                return 0; // needed for completeness
            }

            private void AddRange(int min, int max)
            {
                // no need to add the range if it doesn't contain any items
                Range rng = new Range { min = min, max = max };
                if (rng.Count() > 0)
                    ranges.Add(rng);

                ranges = ranges.OrderBy(r => r.Count()).ToList();
            }
        }

     

     

     

     

     

     

     


    "The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination." - Fred Brooks
    Friday, October 14, 2011 9:46 AM
  • How can that guarantee that "x" will not be swapped back again?

    Because the moving index pointer (i) is the starting point for the call to Next(i, len) :)
    Mark the best replies as Answers! | Blog: http://devpinoy.org/blogs/cvega
    Friday, October 14, 2011 10:03 AM
  • For those solutions that are based on creating an array/list with values from 0-20 and then picking random pointers in the shrinking array/list I have 3 issues with it:

     

    1) The infinity run time scenario is not a practical solution and only exists in theory and sci-fi novels.

    2) It is more complex.  Complex code is not as good as simple code that effectively does the same job.

    3) The solution does not scale well in some scenarios.  To be extreme, lets say I want a random number between 0 to 2,147,483,647??? 0 to 9,223,372,036,854,775,806???

     

    CountryStyle


    Friday, October 14, 2011 12:14 PM
  • "It's not true that they are O(infinity) solutions - that would mean that they ALWAYS took an infinite amount of time to run, which clearly is not the case.

    You would have to run the function an infinite amount of times to actually see one of the calls TAKE an infinite amount of time, which sounds somewhat paradoxical I'll admit. ;)

    The actual O(X) will be asymptotic to some value, but I lack the time (and the mathematical skills!) to actually work out the asymptotic value - it's a lot less than infinity, that's for sure. :)"

    O(infinity) means that the worst case is an infinite amount of time, which is true.  The average time is not infinite, and it can be statistically calculated.

    As to how much of a problem it is, it depends on the data.  It depends partly on what percent of numbers are chosen of the possible options, and how many options there are.  To use someone else's example:

    "3) The solution does not scale well in some scenarios.  To be extreme, lets say I want a random number between 0 to 2,147,483,647??? 0 to 9,223,372,036,854,775,806???"

    If you want to pick 5 non-duplicates from 2,147,483,647 numbers, I agree with you completely.  The odds of getting even a single duplicate on your first pick (barring a really poor random number generator) is quite low, let alone getting enough duplicates to actually slow down your program.  But what if you want  2,147,483,642 random non-duplicated numbers out of a possible  2,147,483,647 numbers?  Then your odds of finishing in any reasonable amount of time are quite slow.  You'll get through a lot rather quickly, but it will take longer and longer to pick the next number.  Just imagine the odds on picking the last few alone, without even considering getting to that point.

    To be honest, I'm just surprised that this isn't such a common problem that there are know and proven solutions that are not overly complicated and are extremely salable and versatile.

    Friday, October 14, 2011 2:23 PM
  • To be honest, I'm just surprised that this isn't such a common problem that there are know and proven solutions that are not overly complicated and are extremely salable and versatile.

    It is not a common problem.  Drawing numbers, replacing them, drawing again and then removing duplicates isn't a common scenario.  The common scenarios are drawing without replacement and drawing from a shuffled array.  These scenarios have well proven solutions.
    Friday, October 14, 2011 2:36 PM
  • It is not a common problem.  Drawing numbers, replacing them, drawing again and then removing duplicates isn't a common scenario.  The common scenarios are drawing without replacement and drawing from a shuffled array.  These scenarios have well proven solutions.

    By common problem I merely meant a series of random non-duplicated random numbers from a range.

    Shuffling an array can work very efficiently for certain parameters, and is extremely inefficient for others, as a solution to said problem.

    Friday, October 14, 2011 4:02 PM
  • using System;
    using System.Collections.Generic;
    using System.Text;
    
    namespace SharxXTestConsole
    {
        //
        // Program
        //
        class Program
        {
            private static Randomizer randomizer = new Randomizer();
    
            static void Main(string[] args)
            {
                Console.WriteLine("Test 1: Generate 3 unique random numbers");
                Console.ReadKey();
    
                int A = randomizer.Next(1, 30);
                int B = randomizer.Next(1, 30);
                int C = randomizer.Next(1, 30);
    
                Console.WriteLine(A);
                Console.WriteLine(B);
                Console.WriteLine(C);
                Console.ReadKey();
    
                Console.WriteLine("Test 2: Generate 20 unique random numbers");
                Console.ReadKey();
                randomizer.Reset();
                for (int i = 0; i < 20; i++)
                {
                    Console.WriteLine(randomizer.Next(1,100));
                }
                Console.ReadKey();
            }
        }
    
        //
        // Randomizer
        //
        public class Randomizer : Random
        {
            List<int> returnedNumbers = new List<int>();
    
            public void Reset()
            {
                returnedNumbers.Clear();
            }
    
            private bool IsUnique(int number)
            {
                lock (returnedNumbers)
                {
                    if (returnedNumbers.Contains(number))
                    {
                        return false;
                    }
                    else
                    {
                        returnedNumbers.Add(number);
                        return true;
                    }
                }
            }
        
            public override int Next()
            {
                int number = base.Next();
                while (!IsUnique(number))
                {
                    number = base.Next();
                }
                return number;
            }
    
            public override int Next(int maxValue)
            {
                int number = base.Next(maxValue);
    
                while (!IsUnique(number))
                {
                    number = base.Next();
                }
                return number;
            }
    
            public override int Next(int minValue, int maxValue)
            {
                int number = base.Next(minValue, maxValue);
                while (!IsUnique(number))
                {
                    number = base.Next(minValue, maxValue);
                }
                return number;
            }
        }
    }
    
    

    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:43 AM
    Friday, October 14, 2011 11:17 PM
  • Shuffling an array can work very efficiently for certain parameters, and is extremely inefficient for others, as a solution to said problem.
    Different scenarios have different solution. From the top question, the original poster is asking simply how to generate 3 unique random numbers between 1 to 20. Shuffling an array, or removal from entry should be the best solution for that.

    Shuffling an array is a practice very well known in card-game programs, as well as other similar games, like dice, dominoes etc..

    If there's a need to draw a completely unique random number from big range, then condition checking should be enough, or simply use Environment.TickCount, or write a class that remembers what was previously returned. All of these solutions have examples in this thread.
    Mark the best replies as Answers! | Blog: http://devpinoy.org/blogs/cvega
    Tuesday, October 18, 2011 2:20 AM
  • Different scenarios have different solution. From the top question, the original poster is asking simply how to generate 3 unique random numbers between 1 to 20. Shuffling an array, or removal from entry should be the best solution for that.

    Shuffling an array is a practice very well known in card-game programs, as well as other similar games, like dice, dominoes etc..

    You are correct, most of the solutions here are sufficient for the specific parameters that the OP has used.  I still consider it worthwhile to find a solution of the problem that is appropriate for a wider variety of input parameters.

    You are correct, shuffling an array would be quire effective for card games, or other similar games as you are choosing from a small set of numbers.  If you can ensure (as you can in those cases) that you aren't ever choosing from a large set of numbers that is the best solution to the problem.  That doesn't mean that there are never situations where you are choosing from a large set of numbers.  (Additionally if you're choosing from a non-finite set of numbers, then shuffling is impossible).

    If there's a need to draw a completely unique random number from big range, then condition checking should be enough, or simply use Environment.TickCount, or write a class that remembers what was previously returned. All of these solutions have examples in this thread.

    Yes, and all of those examples are completely awful if you're choosing a large number of numbers from a large range of numbers.

    For all of the types of solutions here there is a set of input parameters (range and numbers needed) for which they are most efficient.  There are also ranges of solutions for which none of the solutions here are efficient.  Additionally none of the solutions here are reasonably efficient for any of the input situations another problem can solve well.  It sounds like you're advocating something along the lines of: "if my input parameters look like X, use algorithm A, if they look like Y, use algorithm B".  I would like to have algorithm C that was at least reasonably efficient all of the time, so I don't need to use any other or try to determine which is best in the current situation.

    Tuesday, October 18, 2011 1:47 PM
  •  I would like to have algorithm C that was at least reasonably efficient all of the time, so I don't need to use any other or try to determine which is best in the current situation.

    It doesn't look it would be too hard to write a front-end that (based on the parameters passed to it) decides among several algorithms to use to give the best performance. You might have to run some instrumented tests to determine the optimum criteria for deciding which algorithm to use.


    Tuesday, October 18, 2011 4:40 PM
  • In that post I specifically said I was interested in finding a solution that didn't do that.  I was hoping that there was a single algorithm that would work that wasn't a "if the input looks like this then use this algorithm otherwise use that algorithm".  I could live with the latter if it really was the best option, but my open question to the community was, is there actually a better algorithm than anything here that works effectively all/most of the time.  From the responses to this thread, either it does not exist or at a minimum nobody knows of one.  That's okay, if that really is the answer, as long as people understand the pitfalls of that answer.
    Tuesday, October 18, 2011 4:52 PM
  • I think the scope of the requirement is probably too wide to have a single algorithm that would suit all the inputs. That's pretty common with algorithms though. I really wouldn't expect to find a single algorithm that would be best for very small AND very large ranges.

    Tuesday, October 18, 2011 7:04 PM
  • The algorithm should be based upon the statisics being modeled.  Typically selection without duplicates applies to small ranges (lotteries).  Selection with rejection of duplicates typically applies to large ranges (political polls).
    Tuesday, October 18, 2011 7:09 PM
  • The problem - "nCr": From N items, randomly select R.

    Algorithms:

    Let [items] be the set of items to choose from.
    Let [output] be the set of randomly chosen items.

    (1) To choose each item:
        Randomly remove an item from [items];
        Add the removed item to [output].
       
    (2) To choose each item:
        Randomly select an item from [items];
        If it does not exist in [output], add it to [output].
       
    (3) Shuffle [items]. Copy the first R elements of [items] to [output].

    Each of the above can be implemented with a List or a Dictionary for
    [items] and [output].

    My wild stab in the dark:

    * If N and R are BOTH extremely large, then none of these algorithms work.

    * If R/N < 0.2 choose (2).

    * If R/N > 0.5, I choose (3).

    * Otherwise choose (1).

    I'm going to write some code to try this at some point when I get time. ;)
    Tuesday, October 18, 2011 8:03 PM
  • Yes, and all of those examples are completely awful if you're choosing a large number of numbers from a large range of numbers.
    Like what I've said, different scenarios have different solution :)
    I don't think there's a general solution that fits every scenario.

    Here's a code (extracted from a simulation game we'd developed last year, uses the shuffle array technique) that draw 255 unique values from a large range (uint.MaxValue):

    var r = new Random();
    var s = Enumerable.Range(0x00, 0xff);
    
    // shuffle a large set of int.MaxValue
    var hh = s.OrderBy(x => r.Next()).ToArray();
    var hl = s.OrderBy(x => r.Next()).ToArray();
    var lh = s.OrderBy(x => r.Next()).ToArray();
    var ll = s.OrderBy(x => r.Next()).ToArray();
    
    // Draw 255 unique unsigned integers from 0 to uint.MaxValue
    var ints = new uint[255];
    for (var i = 0; i < 255; i++)
    	ints[i] = (uint)(hh[i] << 24 | hl[i] << 16 | lh[i] << 8 | ll[i]);
    
    // Print them
    for (var i = 0; i < 255; i++)
    	Console.WriteLine(ints[i]);
    

     If you want to draw larger than 255, then instead of bytes make then array of words.

    Mark the best replies as Answers! | Blog: http://devpinoy.org/blogs/cvega
    • Marked as answer by Bob Wu-MT Wednesday, October 26, 2011 7:43 AM
    Wednesday, October 19, 2011 5:49 AM