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

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 2

public static class DictionaryExtensions
{
    public static TKey[] Shuffle<TKey, TValue>(
       this System.Collections.Generic.Dictionary<TKey, TValue> source)
    {
        Random r = new Random();
        TKey[] wviTKey = new TKey[source.Count];
        source.Keys.CopyTo(wviTKey, 0);

        for (int i = wviTKey.Length; i > 1; i--)
        {
            int k = r.Next(i);
            TKey temp = wviTKey[k];
            wviTKey[k] = wviTKey[i - 1];
            wviTKey[i - 1] = temp;
        }

        return wviTKey;
    }
}

Sample

            // Using
            System.Collections.Generic.Dictionary<object, object> myDictionary = new System.Collections.Generic.Dictionary<object, object>();
            // myDictionary.Add(myObjectKey1, myObjectValue1); // Sample
            // myDictionary.Add(myObjectKey2, myObjectValue2); // Sample
            // myDictionary.Add(myObjectKey3, myObjectValue3); // Sample
            // myDictionary.Add(myObjectKey4, myObjectValue4); // Sample

            // var myShufledKeys = myDictionary.Shuffle(); // Sample
            // var myShufledValue = myDictionary[myShufledKeys[0]]; // Sample

            // Easy Sample
            var myObjects = System.Linq.Enumerable.Range(0, 4);
            foreach(int i in myObjects)
                myDictionary.Add(i, string.Format("myValueObjectNumber: {0}", i));

            var myShufledKeys = myDictionary.Shuffle();
            var myShufledValue = myDictionary[myShufledKeys[0]];

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

Updated to use generics, be even faster, and with an explanation of why this option is faster.

This answer is similar to the other responses, but since you said you need "a number of random elements" this will be more performant:

public IEnumerable<TValue> RandomValues<TKey, TValue>(IDictionary<TKey, TValue> dict)
{
    Random rand = new Random();
    List<TValue> values = Enumerable.ToList(dict.Values);
    int size = dict.Count;
    while(true)
    {
        yield return values[rand.Next(size)];
    }
}

You can use this method like so:

Dictionary<string, object> dict = GetDictionary();
foreach (object value in RandomValues(dict).Take(10))
{
    Console.WriteLine(value);
}

This has performance improvements over the other responses (including yshuditelu's response).

1. It doesn't have to create a new collection of all of the dictionary's elements each time you want to fetch a new random value. This is a really big deal if your dictionary has a lot of elements in it.
2. It doesn't have to perform a lookup based on the Dictionary's key each time you fetch a random value. Not as big a deal as #1, but it's still over twice as fast this way.

My tests show that with 1000 objects in the dictionary, this method goes about 70 times faster than the other suggested methods.

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);

Answer 6

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 7

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;