Using Linq to find instances that contain a set of objects

Question

Lets say I have a set of bags. Each bag contains a set of marbles. I would like to select the bags which contain a specific combination of marbles. What is the most efficient way to do this in linq?

In code:

public enum Marble { Red, Green, Blue}

public class Bag {
    public string Name;
    public List<Marble> contents;
}
var marbles = new[] { Marble.Red, Marble.Green };
 var bags = new [] 
            {new Bag {Name = "Foo", contents = new List<Marble> {Marble.Blue}},
             new Bag {Name = "Bar", contents = new List<Marble> {Marble.Green, Marble.Red}},
             new Bag {Name = "Baz", contents = new List<Marble> {Marble.Red, Marble.Green, Marble.Blue}}
            };

//Output contains only bag Bar
var output = bags.Where(bag => bag.contents.All(x => marbles.Contains(x)) && 
                               marbles.All(x => bag.contents.Contains(x)));

Is there a better way?

p.campbell · Answer 1 · 2010-09-25T03:05:34.677

You've got a great solution already, it appears.

Try with many varied + repeated bags! Your solution is readable enough, and covers the desired business logic.

 var bags = new[] 
        {new Bag {Name = "Foo", contents = new List<Marble> {Marble.Blue}},
         new Bag {Name = "Bar", contents = new List<Marble> {Marble.Green, Marble.Red}},
         new Bag {Name = "Fiz", contents = new List<Marble> {Marble.Red, Marble.Green}},
         new Bag {Name = "REDS", contents = new List<Marble> {Marble.Red, Marble.Red}},
         new Bag {Name = "Biz", contents = new List<Marble> { Marble.Red } }, 
         new Bag {Name = "Griz", contents = new List<Marble> {Marble.Green, Marble.Green, Marble.Blue}},
         new Bag {Name = "Baz", contents = new List<Marble> {Marble.Red, Marble.Green, Marble.Blue}}
        };

~~Not sure why you need the second condition in your Where().~~

This results in the single matching item, Bar.

 var output2 = bags.Where(b => b.contents.All(x => marbles.Contains(x))
                            && b.contents.Count == marbles.Count());

I've been thinking about this for a while. As for why the second where is required, here's a counter example. `new Bag { Name = "Biz", contents = new List { Marble.Red } }`. As far as I can tell, he's looking for set equivalence. — Jeff Mercado, Sep 25 '10 at 02:46
@Jeff indeed. My solution failed the count as well, with 2 reds. :O — p.campbell, Sep 25 '10 at 03:01

Jeff Mercado · Answer 2 · 2010-09-25T03:43:01.093

0

~~Here's an alternative solution. Unsure about the performance though.~~

var output = bags.Where(bag => !bag.contents.Except(marbles).Any());

Not quite right.

You may want to consider changing the collection type from List<Marble> to something like HashSet<Marble>. This will allow you to do this:

var output = bags.Where(bag => bag.contents.SetEqual(marbles));

edited Sep 25 '10 at 03:43

answered Sep 25 '10 at 02:13

Jeff Mercado

129,526
32
251
272

score 0 · Answer 3 · edited May 23 '17 at 12:11

0

Agree with campbell's answer. Another suggestion is "why not use [Flags] attribute instead of List<MyEnum>"? This question may give you some ideas on enum.

edited May 23 '17 at 12:11

Community

1
1

answered Sep 25 '10 at 02:22

Cheng Chen

42,509
16
113
174

score 0 · Answer 4 · answered Sep 25 '10 at 03:20

If you have many bags and you want the greatest performance, you might look at using PLinq:

public enum Marble { Red, Green, Blue }

public struct Bag
{
    public string Name;
    public List<Marble> contents;
}

class Program
{
    static void Main(string[] args)
    {

        var marbles = new[] { Marble.Red, Marble.Green };
        var bags = new [] 
        {new Bag {Name = "Foo", contents = new List<Marble> {Marble.Blue}},
         new Bag {Name = "Bar", contents = new List<Marble> {Marble.Green, Marble.Red}},
         new Bag {Name = "Baz", contents = new List<Marble> {Marble.Red, Marble.Green, Marble.Blue}}
        };

        //Output contains only bag Bar
        var output = bags.AsParallel<Bag>().Where(bag => bag.contents.All(x => marbles.Contains(x)) &&
                                       marbles.All(x => bag.contents.Contains(x)));

        output.ForAll<Bag>(bag => Console.WriteLine(bag.Name));  // "Bar"
    }
}

score 0 · Accepted Answer · edited Sep 29 '10 at 20:34

I think the set substraction operator is the one that does it the way it should have been done in a much cleaner way. I have given both the method call and linq expression way of doing it.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Project
{
    public enum Marble { Red, Green, Blue}

    public class Bag {
        public string Name;
        public List<Marble> contents;
    }

    class Program
    {
        static void Main()
        {
            var marbles = new[] { Marble.Red, Marble.Green };
            var bags = new[] 
            {
                new Bag {Name = "Foo", contents = new List<Marble> {Marble.Blue}},
                new Bag {Name = "Bar", contents = new List<Marble> {Marble.Green, Marble.Red}},
                new Bag {Name = "Baz", contents = new List<Marble> {Marble.Red, Marble.Green, Marble.Blue}},
                new Bag {Name = "Foo", contents = new List<Marble> {Marble.Blue}},
                new Bag {Name = "Bar", contents = new List<Marble> {Marble.Green, Marble.Red}},
                new Bag {Name = "Fiz", contents = new List<Marble> {Marble.Red, Marble.Green}},
                new Bag {Name = "REDS", contents = new List<Marble> {Marble.Red, Marble.Red}},
                new Bag {Name = "Biz", contents = new List<Marble> { Marble.Red } }, 
                new Bag {Name = "Griz", contents = new List<Marble> {Marble.Green, Marble.Green, Marble.Blue}},
                new Bag {Name = "Baz", contents = new List<Marble> {Marble.Red, Marble.Green, Marble.Blue}}
            };

            // the method call version with set substraction operator
            var query_v2 = bags.Where(bag => bag.contents.Except(marbles).Count() == 0 &&
                                             marbles.Except(bag.contents).Count() == 0                                            
                                     );

            // print out the results 
            Console.WriteLine("query_v2...");
            foreach (var bag in query_v2)
            {
                Console.WriteLine(bag.Name);
            }
            Console.WriteLine();

            // Follwowing is a LINQ Expression version
            var linqversion = from bag in bags
                              let diff1 = bag.contents.Except(marbles).Count()
                              let diff2 = marbles.Except(bag.contents).Count()
                              where diff1 == 0 && diff2 == 0 // perfect match ?
                              select bag;

            Console.WriteLine("Linq expression version output...");
            foreach (var bag in linqversion)
            {
                Console.WriteLine(bag.Name);
            }
            Console.ReadLine();
        }
    }
}

score 0 · Answer 6 · answered Sep 25 '10 at 12:52

I think the set substraction operator is the one that does it the way it should have been done in a much cleaner way. I have given both the method call and linq expression way of doing it.

    using System;
    using System.Collections.Generic;
    using System.Linq;


    namespace Project
    {
            public enum Marble { Red, Green, Blue}

            public class Bag {
                public string Name;
                public List<Marble> contents;
            }




    class Program
    {

        static void Main()
        {

            var marbles = new[] { Marble.Red, Marble.Green };
            var bags = new[] 
                    {new Bag {Name = "Foo", contents = new List<Marble> {Marble.Blue}},
                     new Bag {Name = "Bar", contents = new List<Marble> {Marble.Green, Marble.Red}},
                     new Bag {Name = "Baz", contents = new List<Marble> {Marble.Red, Marble.Green, Marble.Blue}},
                     new Bag {Name = "Foo", contents = new List<Marble> {Marble.Blue}},
                     new Bag {Name = "Bar", contents = new List<Marble> {Marble.Green, Marble.Red}},
                     new Bag {Name = "Fiz", contents = new List<Marble> {Marble.Red, Marble.Green}},
                     new Bag {Name = "REDS", contents = new List<Marble> {Marble.Red, Marble.Red}},
                     new Bag {Name = "Biz", contents = new List<Marble> { Marble.Red } }, 
                     new Bag {Name = "Griz", contents = new List<Marble> {Marble.Green, Marble.Green, Marble.Blue}},
                     new Bag {Name = "Baz", contents = new List<Marble> {Marble.Red, Marble.Green, Marble.Blue}}
                    };





          // the method call version with set substraction   operator

           var  query_v2      = bags.Where(bag => bag.contents.Except(marbles).Count() == 0 &&
                                           marbles.Except(bag.contents).Count() == 0                                            
                                    );



               // print out the results 

               Console.WriteLine("query_v2...");

               foreach (var bag in query_v2)
               {
                   Console.WriteLine(bag.Name);
               }



           Console.WriteLine();








           // Follwowing is a LINQ Expression version
           //
           var linqversion = from bag in bags
                             let diff1 = bag.contents.Except(marbles).Count()
                             let diff2 = marbles.Except(bag.contents).Count()
                             where diff1 == 0 && diff2 == 0 // perfect match ?
                             select bag;


           Console.WriteLine("Linq expression version output...");

            foreach (var bag in linqversion)
            {
                Console.WriteLine(bag.Name);
            }


            Console.ReadLine();
        }









    }

}

Using Linq to find instances that contain a set of objects

6 Answers6