<p>Given the following:</p>

<pre><code>List&lt;List&lt;Option&gt;&gt; optionLists;
</code></pre>

<p>what would be a quick way to determine the subset of Option objects that appear in all N lists? Equality is determined through some string property such as option1.Value == option2.Value.</p>

<p>So we should end up with <code>List&lt;Option&gt;</code> where each item appears only once.</p>

[{'answer_id': 41175, 'author': 'Matt Hamilton', 'author_id': 615, 'author_profile': 'https://Stackoverflow.com/users/615', 'pm_score': 4, 'selected': True, 'text': '<p>Ok, this will find the list of Option objects that have a Value appearing in <em>every</em> list.</p>\n\n<pre><code>var x = from list in optionLists\n        from option in list\n        where optionLists.All(l =&gt; l.Any(o =&gt; o.Value == option.Value))\n        orderby option.Value\n        select option;\n</code></pre>\n\n<p>It doesn\'t do a "distinct" select so it\'ll return multiple Option objects, some of them with the same Value.</p>\n'}, {'answer_id': 41286, 'author': 'Lasse V. Karlsen', 'author_id': 267, 'author_profile': 'https://Stackoverflow.com/users/267', 'pm_score': 0, 'selected': False, 'text': '<p>Sort, then do something akin to a merge-sort.</p>\n\n<p>Basically you would do this:</p>\n\n<ol>\n<li>Retrieve the first item from each list</li>\n<li>Compare the items, if equal, output</li>\n<li>If any of the items are before the others, sort-wise, retrieve a new item from the corresponding list to replace it, otherwise, retrieve new items to replace them all, from all the list</li>\n<li>As long as you still got items, go back to 2.</li>\n</ol>\n'}, {'answer_id': 41318, 'author': 'sven', 'author_id': 46, 'author_profile': 'https://Stackoverflow.com/users/46', 'pm_score': 1, 'selected': False, 'text': '<p>what about using a <em><a href="http://msdn.microsoft.com/en-us/library/bb359438.aspx" rel="nofollow noreferrer">hashSet</a></em>? that way you can do what you want in O(n) where n is the number of items in all the lists combined, and I think that\'s the fastest way to do it.</p>\n\n<p>you just have to iterate over every list and insert the values you find into the hashset\nWhen you insert a key that already exists you will receive <em>false</em> as the return value of the <a href="http://msdn.microsoft.com/en-us/library/bb353005.aspx" rel="nofollow noreferrer">.add method,</a> otherwise <em>true</em> is returned</p>\n'}, {'answer_id': 41327, 'author': 'Skizz', 'author_id': 1898, 'author_profile': 'https://Stackoverflow.com/users/1898', 'pm_score': 2, 'selected': False, 'text': '<p>Here\'s a much more efficent implementation:</p>\n\n<pre><code>static SortedDictionary&lt;T,bool&gt;.KeyCollection FindCommon&lt;T&gt; (List&lt;List&lt;T&gt;&gt; items)\n{\n  SortedDictionary&lt;T, bool&gt;\n    current_common = new SortedDictionary&lt;T, bool&gt; (),\n    common = new SortedDictionary&lt;T, bool&gt; ();\n\n  foreach (List&lt;T&gt; list in items)\n  {\n    if (current_common.Count == 0)\n    {\n      foreach (T item in list)\n      {\n        common [item] = true;\n      }\n    }\n    else\n    {\n      foreach (T item in list)\n      {\n        if (current_common.ContainsKey(item))\n          common[item] = true;\n        else\n          common[item] = false;\n      }\n    }\n\n    if (common.Count == 0)\n    {\n      current_common.Clear ();\n      break;\n    }\n\n    SortedDictionary&lt;T, bool&gt;\n      swap = current_common;\n\n    current_common = common;\n    common = swap;\n    common.Clear ();\n  }\n\n  return current_common.Keys;\n}    \n</code></pre>\n\n<p>It works by creating a set of all items common to all lists processed so far and comparing each list with this set, creating a temporary set of the items common to the current list and the list of common items so far. Effectively an O(n.m) where n is the number of lists and m the number of items in the lists.</p>\n\n<p>An example of using it:</p>\n\n<pre><code>static void Main (string [] args)\n{\n  Random\n    random = new Random();\n\n  List&lt;List&lt;int&gt;&gt;\n    items = new List&lt;List&lt;int&gt;&gt;();\n\n  for (int i = 0 ; i &lt; 10 ; ++i)\n  {\n    List&lt;int&gt;\n      list = new List&lt;int&gt; ();\n\n    items.Add (list);\n\n    for (int j = 0 ; j &lt; 100 ; ++j)\n    {\n      list.Add (random.Next (70));\n    }\n  }\n\n  SortedDictionary&lt;int, bool&gt;.KeyCollection\n    common = FindCommon (items);\n\n  foreach (List&lt;int&gt; list in items)\n  {\n    list.Sort ();\n  }\n\n  for (int i = 0 ; i &lt; 100 ; ++i)\n  {\n    for (int j = 0 ; j &lt; 10 ; ++j)\n    {\n      System.Diagnostics.Trace.Write (String.Format ("{0,-4:D} ", items [j] [i]));\n    }\n\n    System.Diagnostics.Trace.WriteLine ("");\n  }\n\n  foreach (int item in common)\n  {\n    System.Diagnostics.Trace.WriteLine (String.Format ("{0,-4:D} ", item));\n  }\n}\n</code></pre>\n'}, {'answer_id': 42288, 'author': 'Anthony Mastrean', 'author_id': 3619, 'author_profile': 'https://Stackoverflow.com/users/3619', 'pm_score': 0, 'selected': False, 'text': '<p>I don\'t have the performance stats, but if you don\'t want to roll your own method, various collections libraries have a \'Set\' or \'Set(T)\' object that offer the usual set procedures. (listed in the order I would use them).</p>\n\n<ol>\n<li><a href="http://www.codeproject.com/KB/recipes/GenericISet.aspx" rel="nofollow noreferrer">IESI Collections</a> (literally just Set classes)</li>\n<li><a href="http://www.codeplex.com/PowerCollections" rel="nofollow noreferrer">PowerCollections</a> (not updated in a while)</li>\n<li><a href="http://www.itu.dk/research/c5/" rel="nofollow noreferrer">C5</a> (never personally used)</li>\n</ol>\n'}, {'answer_id': 42941, 'author': 'Emperor XLII', 'author_id': 2495, 'author_profile': 'https://Stackoverflow.com/users/2495', 'pm_score': 2, 'selected': False, 'text': '<p>Building on <a href="https://stackoverflow.com/questions/41159/fastest-way-to-find-common-items-across-multiple-lists-in-c#41175">Matt\'s answer</a>, since we are only interested in options that all lists have in common, we can simply check for any options in the first list that the others share:</p>\n\n<pre><code>var sharedOptions =\n    from option in optionLists.First( ).Distinct( )\n    where optionLists.Skip( 1 ).All( l =&gt; l.Contains( option ) )\n    select option;\n</code></pre>\n\n<p>If an option list cannot contain duplicate entires, the <code>Distinct</code> call is unnecessary. If the lists vary greatly in size, it would be better to iterate over the options in the shortest list, rather than whatever list happens to be <code>First</code>. Sorted or hashed collections could be used to improve the lookup time of the <code>Contains</code> call, though it should not make much difference for a moderate number of items.</p>\n'}, {'answer_id': 18097168, 'author': 'logicnp', 'author_id': 51919, 'author_profile': 'https://Stackoverflow.com/users/51919', 'pm_score': 0, 'selected': False, 'text': '<p>You can do this by counting occurrences of all items in all lists - those items whose occurrence count is equal to the number of lists, are common to all lists:</p>\n\n<pre><code>    static List&lt;T&gt; FindCommon&lt;T&gt;(IEnumerable&lt;List&lt;T&gt;&gt; lists)\n    {\n        Dictionary&lt;T, int&gt; map = new Dictionary&lt;T, int&gt;();\n        int listCount = 0; // number of lists\n\n        foreach (IEnumerable&lt;T&gt; list in lists)\n        {\n            listCount++;\n            foreach (T item in list)\n            {\n                // Item encountered, increment count\n                int currCount;\n                if (!map.TryGetValue(item, out currCount))\n                    currCount = 0;\n\n                currCount++;\n                map[item] = currCount;\n            }\n        }\n\n        List&lt;T&gt; result= new List&lt;T&gt;();\n        foreach (KeyValuePair&lt;T,int&gt; kvp in map)\n        {\n            // Items whose occurrence count is equal to the number of lists are common to all the lists\n            if (kvp.Value == listCount)\n                result.Add(kvp.Key);\n        }\n\n        return result;\n    }\n</code></pre>\n'}, {'answer_id': 45240713, 'author': 'user2102327', 'author_id': 2102327, 'author_profile': 'https://Stackoverflow.com/users/2102327', 'pm_score': 0, 'selected': False, 'text': '<pre><code>/// &lt;summary&gt;\n    /// The method FindCommonItems, returns a list of all the COMMON ITEMS in the lists contained in the listOfLists.\n    /// The method expects lists containing NO DUPLICATE ITEMS.\n    /// &lt;/summary&gt;\n    /// &lt;typeparam name="T"&gt;&lt;/typeparam&gt;\n    /// &lt;param name="allSets"&gt;&lt;/param&gt;\n    /// &lt;returns&gt;&lt;/returns&gt;\n    public static List&lt;T&gt; FindCommonItems&lt;T&gt;(IEnumerable&lt;List&lt;T&gt;&gt; allSets)\n    {\n        Dictionary&lt;T, int&gt; map = new Dictionary&lt;T, int&gt;();\n        int listCount = 0; // Number of lists.\n        foreach (IEnumerable&lt;T&gt; currentSet in allSets)\n        {\n            int itemsCount = currentSet.ToList().Count;\n            HashSet&lt;T&gt; uniqueItems = new HashSet&lt;T&gt;();\n            bool duplicateItemEncountered = false;\n            listCount++;\n            foreach (T item in currentSet)\n            {\n                if (!uniqueItems.Add(item))\n                {\n                    duplicateItemEncountered = true;\n                }                        \n                if (map.ContainsKey(item))\n                {\n                    map[item]++;\n                } \n                else\n                {\n                    map.Add(item, 1);\n                }\n            }\n            if (duplicateItemEncountered)\n            {\n                uniqueItems.Clear();\n                List&lt;T&gt; duplicateItems = new List&lt;T&gt;();\n                StringBuilder currentSetItems = new StringBuilder();\n                List&lt;T&gt; currentSetAsList = new List&lt;T&gt;(currentSet);\n                for (int i = 0; i &lt; itemsCount; i++)\n                {\n                    T currentItem = currentSetAsList[i];\n                    if (!uniqueItems.Add(currentItem))\n                    {\n                        duplicateItems.Add(currentItem);\n                    }\n                    currentSetItems.Append(currentItem);\n                    if (i &lt; itemsCount - 1)\n                    {\n                        currentSetItems.Append(", ");\n                    }\n                }\n                StringBuilder duplicateItemsNamesEnumeration = new StringBuilder();\n                int j = 0;\n                foreach (T item in duplicateItems)\n                {\n                    duplicateItemsNamesEnumeration.Append(item.ToString());\n                    if (j &lt; uniqueItems.Count - 1)\n                    {\n                        duplicateItemsNamesEnumeration.Append(", ");\n                    }\n                }\n                throw new Exception("The list " + currentSetItems.ToString() + " contains the following duplicate items: " + duplicateItemsNamesEnumeration.ToString());\n            }\n        }\n        List&lt;T&gt; result= new List&lt;T&gt;();\n        foreach (KeyValuePair&lt;T, int&gt; itemAndItsCount in map)\n        {\n            if (itemAndItsCount.Value == listCount) // Items whose occurrence count is equal to the number of lists are common to all the lists.\n            {\n                result.Add(itemAndItsCount.Key);\n            }\n        }\n\n        return result;\n    }\n</code></pre>\n'}, {'answer_id': 45251772, 'author': 'user2102327', 'author_id': 2102327, 'author_profile': 'https://Stackoverflow.com/users/2102327', 'pm_score': 0, 'selected': False, 'text': '<p>@Skizz The method is not correct. It returns also items that are not common to all the lists in items.\nHere is the corrected method:</p>\n\n<pre><code>/// &lt;summary&gt;.\n    /// The method FindAllCommonItemsInAllTheLists, returns a HashSet that contains all the common items in the lists contained in the listOfLists,\n    /// regardless of the order of the items in the various lists.\n    /// &lt;/summary&gt;\n    /// &lt;typeparam name="T"&gt;&lt;/typeparam&gt;\n    /// &lt;param name="listOfLists"&gt;&lt;/param&gt;\n    /// &lt;returns&gt;&lt;/returns&gt;\n    public static HashSet&lt;T&gt; FindAllCommonItemsInAllTheLists&lt;T&gt;(List&lt;List&lt;T&gt;&gt; listOfLists)\n    {\n        if (listOfLists == null || listOfLists.Count == 0)\n        {\n            return null;\n        }\n        HashSet&lt;T&gt; currentCommon = new HashSet&lt;T&gt;();\n        HashSet&lt;T&gt; common = new HashSet&lt;T&gt;();\n\n        foreach (List&lt;T&gt; currentList in listOfLists)\n        {\n            if (currentCommon.Count == 0)\n            {\n                foreach (T item in currentList)\n                {\n                    common.Add(item);\n                }\n            }\n            else\n            {\n                foreach (T item in currentList)\n                {\n                    if (currentCommon.Contains(item))\n                    {\n                        common.Add(item);\n                    }\n                }\n            }\n            if (common.Count == 0)\n            {\n                currentCommon.Clear();\n                break;\n            }\n            currentCommon.Clear(); // Empty currentCommon for a new iteration.\n            foreach (T item in common) /* Copy all the items contained in common to currentCommon. \n                                        *            currentCommon = common; \n                                        * does not work because thus currentCommon and common would point at the same object and \n                                        * the next statement: \n                                        *            common.Clear();\n                                        * will also clear currentCommon.\n                                        */\n            {\n                if (!currentCommon.Contains(item))\n                {\n                    currentCommon.Add(item);\n                }\n            }\n            common.Clear();\n        }\n\n        return currentCommon;\n    }\n</code></pre>\n'}, {'answer_id': 46712990, 'author': 'birdus', 'author_id': 220899, 'author_profile': 'https://Stackoverflow.com/users/220899', 'pm_score': 0, 'selected': False, 'text': "<p>After searching the 'net and not really coming up with something I liked (or that worked), I slept on it and came up with this. My <code>SearchResult</code> is similar to your <code>Option</code>. It has an <code>EmployeeId</code> in it and that's the thing I need to be common across lists. I return all records that have an <code>EmployeeId</code> in every list. It's not fancy, but it's simple and easy to understand, just what I like. For small lists (my case) it should perform just fine—and anyone can understand it!</p>\n\n<pre><code>private List&lt;SearchResult&gt; GetFinalSearchResults(IEnumerable&lt;IEnumerable&lt;SearchResult&gt;&gt; lists)\n{\n    Dictionary&lt;int, SearchResult&gt; oldList = new Dictionary&lt;int, SearchResult&gt;();\n    Dictionary&lt;int, SearchResult&gt; newList = new Dictionary&lt;int, SearchResult&gt;();\n\n    oldList = lists.First().ToDictionary(x =&gt; x.EmployeeId, x =&gt; x);\n\n    foreach (List&lt;SearchResult&gt; list in lists.Skip(1))\n    {\n        foreach (SearchResult emp in list)\n        {\n            if (oldList.Keys.Contains(emp.EmployeeId))\n            {\n                newList.Add(emp.EmployeeId, emp);\n            }\n        }\n\n        oldList = new Dictionary&lt;int, SearchResult&gt;(newList);\n        newList.Clear();\n    }\n\n    return oldList.Values.ToList();\n}\n</code></pre>\n"}, {'answer_id': 57379638, 'author': 'nawfal', 'author_id': 661933, 'author_profile': 'https://Stackoverflow.com/users/661933', 'pm_score': 2, 'selected': False, 'text': '<p>Fastest to write :)</p>\n\n<pre><code>var subset = optionLists.Aggregate((x, y) =&gt; x.Intersect(y))\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/41159', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/3615/']