0

The following section of code works as I want it to

for (int i = 1; i <= practicehistory.TotalNumQuestions; i++)
{
    query = from a in db.Questions
            where a.CategoryId == practicehistory.CategoryId
            orderby a.QuestionId
            select a;
    randomNumber = random.Next(1, count + 1);
    int qNum = query.Skip(randomNumber - 1).First().QuestionId;
    asked.QuestionId = qNum;
    asked.OrderAsked = i;
    db.AskedHistories.Add(asked);
    db.SaveChanges();
}

However, I am occasionally getting situations where the random number is the same as a random number on a previous for loop run. I wonder then if anyone has an elegant solution to how I can make sure to only generate a random number than has not been previously generated before? I am thinking of populating an array and checking against this but this seems rather redundant!

Marc
  • 3,905
  • 4
  • 21
  • 37
NickP
  • 1,354
  • 1
  • 21
  • 51
  • I guess [shuffling](http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) is what you are looking for. – Save Sep 13 '13 at 20:51
  • What do you mean by "elegant?" How would adding an array to check the values be "redundant" if you are adding new logic to the application? Why wouldn't you do exactly what you have described if it would work? – Mark Hildreth Sep 13 '13 at 20:52
  • [Fisher-Yates shuffle](http://stackoverflow.com/questions/9557883/random-plot-algorithm) – I4V Sep 13 '13 at 20:53
  • I think redundant is a bad choice of works. Rather I mean elegance as it relates to being parsimonious. I understand the solution would work but I may not be aware of an easier way to do it. It just seems like quite a long solution to a simple problem. – NickP Sep 13 '13 at 20:54
  • If you have a fixed number of `practicehistory`s, you're looking for a [shuffle](http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle), not random numbers. – Dour High Arch Sep 13 '13 at 20:54

2 Answers2

7

One way of doing this is to generate the array of possible values (e.g., an array of integers 1 to N), then shuffle them and then iterate through as many of the resulting shuffled values as needed. A quick Google search yields several C# implementations of the Fisher-Yates shuffle if you are interested in coding "by example".

Mark Wilkins
  • 40,729
  • 5
  • 57
  • 110
  • 1
    Thanks, I was unaware of this method and is definitely an elegant way to solve this. – NickP Sep 13 '13 at 20:57
  • C# code found in the answer to this question: http://stackoverflow.com/questions/273313/randomize-a-listt-in-c-sharp – Steve Sep 13 '13 at 20:59
  • @NickP, I agree that it is elegant. I have used it a few different times in my work for various types of tests. It is nice because it is "fair" (unbiased) in the selection. – Mark Wilkins Sep 13 '13 at 21:01
  • @MarkWilkins Definitely more parsimonious than scanning through checking what has already been chosen each time. Much appreciate it! – NickP Sep 13 '13 at 21:03
0

There are two approaches to solving this, checking if the number has been used already, or pre-generate the numbers randomize the order they are stored in and take them out of the list in the "shuffled order".

The first approach is better for when you do not know how many numbers you will need in total or you have a very large pool of numbers and it is unlikely that you will hit collisions from finding the same number multiple times. The disadvantage to this the more percentage of the total numbers available is used the slower the next number generation runs.

//This function will run slower and slower until all numbers have been used and then it will throw a InvalidOperationExecption. 
//You could get a InvalidOperationExecption early if you reuse the ISet for multiple ranges.
public static int NextUnused(this Rand rand, int minValue, int maxValue, ISet<int> usedNumbers)
{
    if(usedNumbers.Count >= maxValue - minValue)
        throw new InvalidOperationExecption("All possible numbers have been used");

    int number;
    do
    {
       number = rand.Next(minValue, maxValue);

    } while(!usedNumbers.Add(number)) //if we have seen the number before it will return false and try again.

    return number;
}

The second approach is better when you know exactly how many object you will need, or there is a small pool of possible choices that could be chosen.

public class RandomRange
{

    public RandomRange(int start, int count) : this(start, count, new Rand())
    {
    }

    public RandomRange(int start, int count, Rand randSource)
    {
        var numberList = new List<int>(Enumerable.Range(start, count);

        Shuffle(numberList);

        _numbers = new Queue<int>(numberList);
    }

    //Will throw a InvalidOperationExecption when you run out of numbers.
    public int GetNextNumber()
    {
        return _numbers.Dequeue();
    }

    private static void Shuffle(List<int> list)
    {
         throw new NotImplementedException("An exercise for the reader");
    }

    private Queue<int> _numbers;
}
Scott Chamberlain
  • 124,994
  • 33
  • 282
  • 431