getting a random number as long as its not in a list

Question

 var list = new List<int>(){1,17,18,21,30};
 Random rnd = new Random(DateTime.Now.Second);
 int r;
 do
 {
     r = rnd.Next(1, 30);
 }
 while (list.Contains(r));

but i think that's a stupid solution, can anyone give me a more optimized approach?

even better if there is a way to prevent the Random instance from returning a number that it has already returned.

in case anyone wonders why do i need this its the first step in shuffling 3 byte arrays and combining them into one byte array and producing 3 byte arrays that hold the indices original order as it was in the original arrays.

I think you want that to read `while (list.Contains(r));` Otherwise it's quite possible that you'll return a number that already exists in the list. — Jim Mischel, Jan 02 '14 at 20:51
@AlexeiLevenkov yes but not just shuffling, its combining multiple byte arrays into one array and shuffling them and in the process filling arrays preserve the order with the index that has been added and from which array, i got it working but i just dont like my above part of the code — user1492051, Jan 02 '14 at 20:52
Something like `class {byte Data; int SourceIndex;int SourceArrayId;}`? Shuffling the way you try to write may take forever... — Alexei Levenkov, Jan 02 '14 at 20:56
About the only thing you can do to improve the code above is to use a `HashSet`. It's likely that your overall algorithm, which forces the ugly code you posted above, could use some improvement. — Jim Mischel, Jan 02 '14 at 20:57
@AlexeiLevenkov yes i have the following object too class ArrayIndex `{ string arrayName { get; set; } int index { get; set; } byte value { get; set; } }` — user1492051, Jan 02 '14 at 20:58
I'm completely puzzled than why you can't use normal shuffling code than. At this point you probably should accept an answer (which answers question as you've asked) and reconsider why you want to invent awfully slow shuffling yourself. — Alexei Levenkov, Jan 02 '14 at 21:07
Alexei is right; it sounds like a better characterization of your problem is "I want to shuffle the set `{ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29}` into a random order; how do I do that? — Eric Lippert, Jan 02 '14 at 22:32
@EricLippert i know how to schuffel i am talking about combining 3 arrays schuffiling that and having additional arrays to indicate the order, its done though and working perfectly — user1492051, Jan 02 '14 at 22:58

Scott Chamberlain · Answer 1 · 2014-01-02T20:48:34.323

Yes, one thing to make it much more efficient is use a HashSet<int> instead of a List<int> lookups for a HashSet are MUCH faster than a List (however the cost of the constructor will be slightly more for a HashSet).

Also if the input list is always the same numbers move it out of the function to help reduce the cost overhead of generating the HashSet the first time.

Due to order now mattering, in my personal experience (please test and profile for your own situation), after about 14 items in the list it is faster to convert a list to a HashSet and do the lookup than doing the lookup in the list itself.

var list = new List<int>(){1,17,18,21,30};
Random rnd = new Random(DateTime.Now.Second);
int r;

//In this example with 5 items in the list the HashSet will be slower do to the cost 
// of creating it, but if we knew that the 5 items where fixed I would make this 
// outside of the function so I would only have to pay the cost once per program 
// start-up and it would be considered faster again due to amortized start-up cost.
var checkHashSet = new HashSet<int>(list); 

do
{
    r = rnd.Next(1, 30);
}
while (checkHashSet.Contains(rnd.Next(1, 30))); //Shouldent this be "r" not "rnd.Next(1,30)"?

+1 for answer to the question, but I believe OP needs [shuffling code](http://stackoverflow.com/questions/273313/randomize-a-listt-in-c-sharp/1262619#1262619), not what the question is actually about. — Alexei Levenkov, Jan 02 '14 at 20:49

score 3 · Accepted Answer · edited May 23 '17 at 10:32

You're right that looping isn't particularly efficient. You can use some handy extensions to select a number if you consider the constraint of the list of valid numbers, as opposed to the list of invalid ones.

So you have your list of invalid numbers:

var list = new List<int>(){1,17,18,21,30};

Which means that your list of valid numbers is the range from 1-30 except for these. Something like:

var validList = Enumerable.Range(1, 30).Except(list);

So we can use these extensions from the linked answer:

public static T RandomElement(this IEnumerable<T> enumerable)
{
    return enumerable.RandomElementUsing(new Random());
}

public static T RandomElementUsing(this IEnumerable<T> enumerable, Random rand)
{
    int index = rand.Next(0, enumerable.Count());
    return enumerable.ElementAt(index);
}

And select a random element from the list of known valid numbers:

var kindOfRandomNumber = Enumerable.Range(1, 30).Except(list).RandomElement();

getting a random number as long as its not in a list

2 Answers2