Adjust random generator range dynamically by excluding numbers?

Question

I want to know if there is possible to perform the following situation:

I generate numbers in a specified range with a Random object, for example:

Random generator = new Random(0, 100);

If I type generator.next(), I get the number 40 (for example). Now, when I type again generator.next(), I want to get a new random number, in the range (0 - 39, 41 - 100). So I want to eliminate the generated numbers from the generator's range.

Is this possible?

If your ultimate goal is to get N random numbers from 0 to 100 without duplicates, this is not quite the way to do it. — Jon, Oct 14 '15 at 18:42
It might be a lot easier to just create a list from 0-100, shuffle the list, and then pop the first element one at a time. — ryanyuyu, Oct 14 '15 at 18:43
Unless you're seriously concerned about the performance, the best way to do this is to store the numbers you've generated so far in a list, and if you happen to roll a number that's already in the list, just skip it and roll again. — Jim, Oct 14 '15 at 18:44
@Jon, perhaps I should have said "easiest way I know how off the top of my head". — Jim, Oct 14 '15 at 18:46
@Jim that seems like a really inefficient way to handle this. You'll inevitably end up with 99 of the 100 random numbers and the code will just sit there spinning all day until it ends up hitting that 100th number — leigero, Oct 14 '15 at 18:48
Yes, I already thought about that and I've seen that it might be inneficient. — Cosmin Ioniță, Oct 14 '15 at 18:49

Janne Matikainen · Answer 1 · 2015-10-14T19:07:50.040

1

This would create count unique random numbers in range of 0 - 100

public IEnumerable<int> Randomize(int count, int seed)
{
    var generator = new Random(seed);

    return Enumerable.Range(0, 100)
      .Select(x => new { Value = x, SortOrder = generator.Next() })
      .OrderBy(x => x.SortOrder)
      .Select(x => x.Value)
      .Take(count);
}

edited Oct 14 '15 at 19:07

answered Oct 14 '15 at 18:59

Janne Matikainen

5,061
15
21

Will this still work in the unlikely but possible event that the generator gives you the same value more than once? – hatchet - done with SOverflow Oct 14 '15 at 19:03
Of course, it is just for the order... – Janne Matikainen Oct 14 '15 at 19:04
1

@hatchet It cases a small bias in the results. `OrderBy` uses a stable sort, so the item earlier in the sequence appears first as a tiebreaker if the sort item is the same. That means that if you're ordering a 2-item list, the first item has a 1/(2^32) greater chance of being the first item in the result. For some people that's a small enough discrepancy from an even sort as to ignore, but it's entirely possible that for certain applications that's a non-negligible deviation from true even distribution. – Servy Oct 14 '15 at 19:14

hatchet - done with SOverflow · Answer 2 · 2015-10-14T19:35:36.917

0

The idea in the code below (not guaranteed to compile...it's off the top of my head), is to make a list of the available numbers, then randomly pick from that list, removing them as they're selected. This avoids excessive generation of random numbers. You only need to generate 99 random numbers. When you get to only one number left, you simply add that one at the end.

var countWanted = 100;
var dest = new List<int>(countWanted);
var source = new List<int>();
for (int i = 0; i < 100 ; i++) source.Add(i);
var r = new Random();
for (int i = 100; i > 100-countWanted; i--)
    var n = r.Next(0,i);
    dest.Add(source[n]);
    source[n] = source[i-1];
}

edited Oct 14 '15 at 19:35

answered Oct 14 '15 at 18:54

hatchet - done with SOverflow

15,919
5
47
57

Note that this is an O(n^2) algorithm for solving this problem that's trivially solvable in O(n) time. – Servy Oct 14 '15 at 19:15
Agreed. But a trivial difference with small n's. I'll fix that anyway. – hatchet - done with SOverflow Oct 14 '15 at 19:25

score 0 · Answer 3 · answered Oct 14 '15 at 19:02

0

You don't even need Random object:

var uniqueRandomNums = Enumerable.Range(0, 100)
                       .OrderBy(n => Guid.NewGuid())
                       .Take(num)
                       .ToList();

answered Oct 14 '15 at 19:02

w.b

11,026
5
30
49

True, didn't think of that, clever. – Janne Matikainen Oct 14 '15 at 19:06
1

GUIDs are not random. – Servy Oct 14 '15 at 19:11
@w.b But GUIDS aren't even designed to *approximate* randomness. `Random` is as close of an approximation to true randomness as is feasible. GUIDs are entirely free to return values that are always sequential (and in fact will do exactly that using certain GUID generation algorithms) which would result in this code always returning the original set. – Servy Oct 14 '15 at 19:19

score 0 · Answer 4 · answered Oct 14 '15 at 19:05

0

A class like this will do it nicely:

using System;
using System.Collections.Generic;

namespace RandomTools
{
    public class NonRepeatingRandom
    {
        private Random _random;
        private List<int> _possibleValues;

        public NonRepeatingRandom(int minValue, int maxValue)
        {
            _random = new Random();
            _possibleValues = new List<int>();

            for (var i = minValue; i < maxValue; i++)
            {
                _possibleValues.Add(i);
            }
        }

        public int Next()
        {
            var possibleValuesCount = _possibleValues.Count;
            if (possibleValuesCount == 0)
            {
                return -1;
            }

            var nextIndex = _random.Next(0, possibleValuesCount);
            var nextValue = _possibleValues[nextIndex];
            _possibleValues.RemoveAt(nextIndex);

            return nextValue;
        }
    }
}

And you can simply use it like this:

using RandomTools;

....

var myRandom = new NonRepeatingRandom(0, 100);
var nextValue = myRandom.Next();

When you've exhausted every possible value, it will return -1.

answered Oct 14 '15 at 19:05

Kennnnnnnn

11
3

Note that this is an O(n^2) algorithm for solving this problem that's trivially solvable in O(n) time. – Servy Oct 14 '15 at 19:15
@Servy Where's the n^2? It loops through the number of items once to generate one of each number—that's *n*. Then it serves them up one at a time, which is also *n*. O(2n) is O(n). – ErikE Oct 14 '15 at 19:20
@ErikE Generating each number, in your example, is an O(n) operation, because you're removing the item from a `List`., and you do that O(n) operation n times, which is O(n^2). – Servy Oct 14 '15 at 19:22
Ah, you're saying List removal is O(n) itself. Okay, thanks. Would a data structure that offers O(1) removal fix the problem (a LinkedList comes to mind)? – ErikE Oct 14 '15 at 19:24
Or a Fisher-Yates shuffle... as long as one realizes that it can be really hard to get equal chance of every possible combination without using a cryptographic-quality RNG with hundreds or thousands of bits of entrpy. – ErikE Oct 14 '15 at 19:26
@ErikE A `LinkedLIst` is O(n) removal as you have to traverse the structure to find the item to remove. – Servy Oct 14 '15 at 19:28
@ErikE A Fisher-Yates shuffle would be an entirely appropriate solution to this problem. Note that your proposed solution has exactly the same problem as that approach in that if your RNG doesn't have sufficient entropy for the data you're shuffling then not all solutions are possible. The solution to that however is to use cryptographically strong RNG, not to use a different shuffling algorithm. – Servy Oct 14 '15 at 19:29
@Servy Clearly I need to stop doing drive-by analysis, and really think about things because it's immediately obvious that a linked list has O(n) traversal. Now about my proposed solution other than Fisher-Yates... what is that? I don't have any other proposed solutions? – ErikE Oct 14 '15 at 20:04
@ErikE There are lots of variations, and other comparable algorithms, but a fisher-yates would be entirely appropriate and more effective than what you've mentioned. – Servy Oct 14 '15 at 20:07
What have I mentioned? Do you mean a `LinkedList`? I haven't mentioned any other solutions. – ErikE Oct 14 '15 at 20:16

score -2 · Answer 5 · answered Oct 14 '15 at 18:45

-2

Make a list of integers

var myList = new List<int>();
var myrandom = new Random();

When you need a random, do this:

int newRandom;
while(true){
    newRandom = myrandom.Next(0,100);
    if (!myList.Contains(newRandom)){
        myList.Add(newRandom);
        break;
    }
}
//continue execution here
System.Diagnostics.Debug.Print(newRandom);

answered Oct 14 '15 at 18:45

Xavier J

4,326
1
14
25

This will work, but should not be used if you're even remotely concerned about efficiency. This relies on luck/chance to eventually land a number you don't already have. – leigero Oct 14 '15 at 18:50
A SortedList would be more efficient. "Luck"??? – Xavier J Oct 14 '15 at 18:52
@IoniţăCosmin pretty much any solution is better than this, and they are not hard to find. Here's someone who knows a lot explaining: http://stackoverflow.com/questions/2351308/random-number-generator-in-c-sharp-unique-values/2351735#2351735 – Jon Oct 14 '15 at 18:52
Yes luck, what if you wand a number between 0-10 million with the same logic? Eventually you'll have 9,999,999 numbers in your list and you'll be stuck in that loop all day waiting on "luck" to hit the one number you don't yet have. – leigero Oct 14 '15 at 18:54
That's the point of using a SortedList, which coincidentally Jon's example basically covers by implementing a sort. But realistically, the example ONLY specified 100 numbers. K I S S. – Xavier J Oct 14 '15 at 18:56
@codenoire If you want to keep it simple then just re-use an already existing correct and efficient solution to an already solved problem rather than writing your own very poor implementation. – Servy Oct 14 '15 at 19:17

Adjust random generator range dynamically by excluding numbers?

5 Answers5