Random entry from dictionary

Question

What is the best way to get a random entry from a Dictionary in c#?

I need to get a number of random objects from the dictionary to display on a page, however I cannot use the following as dictionaries cannot be accessed by index:

Random rand = new Random();
Dictionary< string, object> dict = GetDictionary();
return dict[rand.Next()];

Any suggestions?

Answer 1

If you're using .net 3.5, Enumerable has an extension method ElementAt which would allow you to do:

return dict.ElementAt(rand.Next(0, dict.Count)).Value;

Answer 2

My other answer is correct for the question, and would be useful in many cases like getting roll information from custom dice (each die's roll is random, independent of the other dice). However, your comments make it sound like you might be hoping to get a series of "unique" elements out of the Dictionary, sort of like dealing cards from a deck. Once a card is dealt, you never want to see the same card again until a re-shuffle. In that case, the best strategy will depend on exactly what you're doing.

If you're only getting a few elements out of a large Dictionary, then you should be able to adapt my other answer, removing the random element from the list each time a new one is retrieved. You'll probably also want to make the list into a LinkedList, because even though it'll be slower to find an item by its index, it's much less expensive to remove elements from the middle of it. The code for this would be a little more complicated, so if you're willing to sacrifice some performance for simplicity you could just do this:

public IEnumerable<TValue> UniqueRandomValues<TKey, TValue>(IDictionary<TKey, TValue> dict)
{
    Random rand = new Random();
    Dictionary<TKey, TValue> values = new Dictionary<TKey, TValue>(dict);
    while(values.Count > 0)
    {
        TKey randomKey = values.Keys.ElementAt(rand.Next(0, values.Count));  // hat tip @yshuditelu 
        TValue randomValue = values[randomKey];
        values.Remove(randomKey);
        yield return randomValue;
    }
}

If, on the other hand, you're planning to pull a significant number of elements from your dictionary (i.e. dealing out more than log(n) of your "deck"), you'll be better off just shuffling your entire deck first, and then pulling from the top:

public IEnumerable<TValue> UniqueRandomValues<TKey, TValue>(IDictionary<TKey, TValue> dict)
{
    // Put the values in random order
    Random rand = new Random();
    LinkedList<TValue> values = new(dict.Values.OrderBy(_ => rand.Next());
    // Remove the values one at a time
    while(values.Count > 0)
    {
        yield return values.Last.Value;
        values.RemoveLast();
    }
}

Credit goes to ookii.org for the simple shuffling code. If this still isn't quite what you were looking for, perhaps you can start a new question with more details about what you're trying to do.

Answer 3

From your dictionary...

Dictionary<string, int> dict = new Dictionary<string, object>()

you can create a complete list of keys...

List<string> keyList = new List<string>(dict.Keys);

and then select a random key from your list.

Random rand = new Random();
string randomKey = keyList[rand.Next(keyList.Count)];

Then simply return the random object matching that key.

return dict[randomKey];

Answer 4

This won't be terribly fast, but it should work:

Random rand = new Random();
Dictionary dict = GetDictionary();
return dict.Skip(rand.Next(dict.Count)).First().Value;

Answer 5

An easy solution would be to use the ToList() extension method and use the index of the list.

If you just need the values or the keys (not the key/value pair) return these collections from the dictionary and use ToList() as well.

        Random rand = new Random();
        Dictionary<string, object> dict = GetDictionary();
        var k = dict.ToList()[rand.Next(dict.Count)];
        // var k = dict.Values.ToList()[rand.Next(dict.Count)];
        // var k = dict.Keys.ToList()[rand.Next(dict.Count)];

        Console.WriteLine("Random dict pair {0} = {1}", k.Key, k.Value);