Get random items with fixed length of different types

Question

I have a List<Fruit>,

public class Fruit
{
    public string Name { get; set; }
    public string Type { get; set; }
}

and the list above contains 30 Fruit objects of two types: Apple and Orange. 20 apples and 10 oranges.

List<Fruit> fruits = new List<Fruit>();
fruits.Add(new Fruit(){ Name = "Red Delicious", Type = "Apple" });
fruits.Add(new Fruit(){ Name = "Granny Smith", Type = "Apple" });
fruits.Add(new Fruit(){ Name = "Sour Granny", Type = "Orange" });
fruits.Add(new Fruit(){ Name = "Delicious Yummy", Type = "Orange" });
.....

How can I get a list of 10 random fruits (from the basket of 30 fruits), but there should be 3 oranges and 7 apples?

Why 3 oranges and 7 apples specifically? – Abion47 Jan 01 '17 at 11:51 — Abion47, Jan 01 '17 at 11:51

score 12 · Accepted Answer · edited Jun 20 '20 at 09:12

12

You can use LINQ and Guid or Random to make a random selection:

var apples = fruits.
     Where( f => f.Type == "Apple" ). //choose only from apples
     OrderBy( f => Guid.NewGuid() ). //order randomly
     Take( 7 ). //take 7 apples
     ToList();

The same goes for oranges, just with "Orange" instead of "Apple" and with 3 instead of 7.

How does it work?

OrderBy sorts the enumerable by the given condition. Because Guid.NewGuid() returns a random unique identifier, the result is that the items are ordered randomly. When we then apply Take( n ), it will take the n first items in this random order.

Note that instead of Guid you can create an instance of Random and the use f => random.NextDouble() as the OrderBy expression. This is potentially a safer solution, because Guid.NewGuid() is not guaranteed to be random, only to be unique.

edited Jun 20 '20 at 09:12

Community

1
1

answered Jan 01 '17 at 11:54

Martin Zikmund

38,440
7
70
91

4

Even though it's not a computer-science question, I would avoid the term "truly random" at all costs – haim770 Jan 01 '17 at 12:02
1

does this code work with the following line: `OrderBy( f => a => Guid.NewGuid() )` – wake-0 Jan 01 '17 at 12:04
1

@Kevin Wallis - Thank you for the observation, I must have thought "twice" :-D – Martin Zikmund Jan 01 '17 at 12:06
I know the .NewGuid generates a new Guid, but how does it randomly select using the OrderBy? I don't understand the magic. – nocturns2 Jan 01 '17 at 12:12
Nice! Thanks for the explanation!! – nocturns2 Jan 01 '17 at 12:18
10

Remember that `Guid.NewGuid()` do not "garantee" "randomness" of the generated guids. Please read comments of Eric Lippert on [this](http://stackoverflow.com/a/3169165/1565525) answer. And then I think you can use approach provided in [this](http://stackoverflow.com/a/1287572/1565525) answer. – Fabio Jan 01 '17 at 12:52
1

@Fabio Contrary to sort where the comparison function can be called repeatedly (and you have to worry about inconsistencies), OrderBy caches the result of the keySelector so the code is correct as-is (although how well documented that is, is another question). Still I don't see any good reason to use `Guid.NewGuid()` instead of the simple `random.Next()`. It's much more efficient and much easier to reason about: The documentation nowhere specifies what type of UUID is generated as far as I can see and really only type 4 would be obviously correct. – Voo Jan 01 '17 at 16:44
This is a very biased randomization in O(n log n). Please use Fisher-Yates shuffling instead, which is O(n) – Drakarah Jan 01 '17 at 16:52
1

@drake Assuming the random generator used for the key selection is as good as the one used for Fisher-Yates, why would this be "very biased"? It is less efficient, but that's perfectly negligible for 30 fruits. – Voo Jan 01 '17 at 17:09
I don't really think time complexity would matter in the case of just 30 items in the list :-) . – Martin Zikmund Jan 01 '17 at 17:12
`Guid.NewGuid()` is **not** guaranteed to be random. – Enigmativity Feb 21 '17 at 23:36

score 5 · Answer 2 · answered Jan 01 '17 at 11:59

First, separate between apples and oranges, so you would have

var apples = basket.Where(f => f.Type == "Apple");
var oranges = basket.Where(f => f.Type == "Orange");

Now in order to a random number of elements without repetition from both lists, you can use something like this:

var random = new Random();
var numOfElements = 7; // Replace this with the number you want
apples.OrderBy(x => random.Next()).Take(numOfElements).ToList();

Finally, combine the two lists you get.

paparazzo · Answer 3 · 2017-01-01T21:16:42.263

You can shuffle once and then peel off the apples and oranges
It will be a little more efficient than random for each fruit but on a short list will not make much difference

public static void TestFruit()
{
    List<Fruit> fruits = new List<Fruit>();
    fruits.Add(new Fruit("01", "orange")); fruits.Add(new Fruit("02", "orange"));
    fruits.Add(new Fruit("03", "orange")); fruits.Add(new Fruit("04", "orange"));
    fruits.Add(new Fruit("05", "orange")); fruits.Add(new Fruit("06", "orange"));
    fruits.Add(new Fruit("07", "orange")); fruits.Add(new Fruit("08", "orange"));
    fruits.Add(new Fruit("09", "orange")); fruits.Add(new Fruit("10", "orange"));
    fruits.Add(new Fruit("01", "apple"));  fruits.Add(new Fruit("02", "apple"));
    fruits.Add(new Fruit("03", "apple"));  fruits.Add(new Fruit("04", "apple"));
    fruits.Add(new Fruit("05", "apple"));  fruits.Add(new Fruit("06", "apple"));
    fruits.Add(new Fruit("07", "apple"));  fruits.Add(new Fruit("08", "apple"));
    fruits.Add(new Fruit("09", "apple"));  fruits.Add(new Fruit("10", "apple"));
    fruits.Add(new Fruit("11", "apple"));  fruits.Add(new Fruit("12", "apple"));
    fruits.Add(new Fruit("13", "apple"));  fruits.Add(new Fruit("14", "apple"));
    fruits.Add(new Fruit("15", "apple"));  fruits.Add(new Fruit("16", "apple"));
    fruits.Add(new Fruit("17", "apple"));  fruits.Add(new Fruit("18", "apple"));
    fruits.Add(new Fruit("19", "apple"));  fruits.Add(new Fruit("20", "apple"));
    Shuffle<Fruit>(fruits);
    List<Fruit> randomFruits = fruits.Where(x => x.Type == "apple").Take(7).ToList();
    randomFruits.AddRange(fruits.Where(x => x.Type == "orange").Take(3));
    foreach (Fruit f in randomFruits)
    {
        Debug.WriteLine("Name {0}  Type {1}", f.Name, f.Type);
    }
    Debug.WriteLine("");
}
public static void Shuffle<T>(List<T> list)
{   // FisherYates 
    for (int i = list.Count - 1; i >= 1; i--)
    {
        int j = rand.Next(i + 1);
        if (j != i)
        {   // exchange values
            T curVal = list[i];
            list[i] = list[j];
            list[j] = curVal;
        }
    }
}
public class Fruit
{
    public string Name { get; set; }
    public string Type { get; set; }
    public Fruit(string name, string type)
    {
        Name = name;
        Type = type;
    }
}

Silly Paparazzi, you don't need to peel apples, you can eat them with the skin left on! — Scott Chamberlain, Jan 01 '17 at 22:00

Get random items with fixed length of different types

3 Answers3

How does it work?