Get a random item from a collection that does not already exist in another collection - LINQ?

Question

Hi,

I am trying to learn LINQ but it is quite confusing at first!

I have a collection of items that have a color property (MyColor). I have another collection of all colors (called AvailableColors - lets say 10 for example).

I want to get a random color from the AvailableColors that does not already exist in my collection.

My current C# code just gets a random color but I would like to rewrite this in LINQ to take in the current color collection and exclude those from the possible options:

public MyColor GetRandomColour()
{
    return AvailableColors[new Random().Next(0, AvailableColors.Count)];
}

so it would take in the existing collection:

public MyColor GetRandomColour(ListOfSomethingWithColorProperty)

Thanks for any pointers!

Answer 1

Excluding already-used colors implies saving of state. You might be better off writing an iterator and using yield return to return the next random color in the sequence. This allows you to "remember" which colors have already been used.

Once you have that, you can call it using Take(1) from Linq, if you wish.

Answer 2

 // assumes Random object is available, preferrably a re-used instance
 Color color = AvailableColors
                 .Except(myItems.Select(item => item.Color).Distinct())
                 .OrderBy(c => random.Next())
                 .FirstOrDefault();

Probably not terribly efficient, but also probably not a concern given a small number of items.

Another approach is to randomly order the available colors once beforehand, therefore you can go in order. Use a List<Color> so you can remove elements as you use them, or save the current index with each pull. Once the list is depleted or the index exceeds the length of the array, notify your user that you're all out of colors.

Answer 3

var rnd = new Random();   // don't keep recreating a Random object.


public MyColor GetRandomColour(List<Something> coll)  
{
   var len = rnd.Next(0, AvailableColors.Count- coll.Count);
   return AvailableColors.Except(coll.Select(s=>s.MyColor)).Skip(len).First();
}

Answer 4

I'm going to suggest that you be Linq-minded and create a good, general purpose IEnumerable<T> extension method that does the heavy lifting you require and then your GetRandomColor functions are simpler and you can use the extension method for other similar tasks.

So, first, define this extension method:

public static IEnumerable<T> SelectRandom<T>(this IEnumerable<T> @this, int take)
{
    if (@this == null)
    {
        return null;
    }
    var count = @this.Count();
    if (count == 0)
    {
        return Enumerable.Empty<T>();
    }
    var rnd = new Random();
    return from _ in Enumerable.Range(0, take)
           let index = rnd.Next(0, count)
           select @this.ElementAt(index);
}

This function allows you to select zero or more randomly chosen elements from any IEnumerable<T>.

Now your GetRandomColor functions are as follows:

public static MyColor GetRandomColour()
{
    return AvailableColors.SelectRandom(1).First();
}

public static MyColor GetRandomColour(IEnumerable<MyColor> except)
{
    return AvailableColors.Except(except).SelectRandom(1).First();
}

The second function accepts an IEnumerable<MyColor> to exclude from your available colors so to call this function you need to select the MyColor property from your collection of items. Since you did not specify the type of this collection I felt it was better to use IEnumerable<MyColor> rather than to make up a type or to define an unnecessary interface.

So, the calling code looks like this now:

var myRandomColor = GetRandomColour(collectionOfItems.Select(o => o.MyColor));

Alternatively, you could just directly rely on Linq and the newly created extension method and do this:

var myRandomColor =
    AvailableColors
    .Except(collectionOfItems.Select(o => o.MyColor))
    .SelectRandom(1)
    .First();

This alternative is more readable and understandable and will aid maintainability of your code. Enjoy.

Answer 5

There's a nifty way to select a random element from a sequence. Here it's implemented as an extention method:

public static T Random<T>(this IEnumerable<T> enumerable)
{
    var rng = new Random(Guid.NewGuid().GetHashCode());
    int totalCount = 0;
    T selected = default(T);

    foreach (var data in enumerable)
    {
        int r = rng.Next(totalCount + 1);
        if (r >= totalCount)
            selected = data;
        totalCount++;
    }
    return selected;
}

This method uses the fact that probability to choose n-th element over m-th when iterating is 1/n.

With this method, you can select your colour in one line:

var color = AvailableColors.Except(UsedColors).Random();