Finding 2 matching sub-lists from list of list

Here's a solution that comes up with your answer. I wouldn't exactly called it efficient, but it's pretty simple to follow.

It breaks the work in two step. First it constructs a list of initial candidates where they have exactly three matches. The second step adds the ListX property and checks to see if the remaining criteria is met.

var matches = allLists.Take(allLists.Count - 1)
    .SelectMany((x, xIdx) => allLists
        .Skip(xIdx + 1)
        .Select(y => new { ListA = x, ListB = y, Shared = x.Intersect(y) })
        .Where(y => y.Shared.Count() == 3))
    .SelectMany(x => allLists
        .Where(y => y != x.ListA && y != x.ListB)
        .Select(y => new 
        { 
             x.ListA, 
             x.ListB, 
             x.Shared, 
             ListX = y, 
             SingleShared = x.Shared.Intersect(y) 
        })
        .Where(y => y.SingleShared.Count() == 1 
            && !allLists.Any(z => z != y.ListA 
                && z != y.ListB 
                && z != y.ListX 
                && z.Intersect(y.Shared).Any())));

You get the output below after running the following code.

ListA. 3: [3, 4, 5, 6, 7, 8, 9] ListB. 5: [5, 7, 9, 11] => [5, 7, 9], ListX. 6:[6, 7, 10] => 7

matches.ToList().ForEach(x => {
    Console.WriteLine("ListA. {0}: [{1}] ListB. {2}: [{3}] => [{4}], ListX. {5}:[{6}] => {7}", 
        allLists.IndexOf(x.ListA), 
        string.Join(", ", x.ListA), 
        allLists.IndexOf(x.ListB), 
        string.Join(", ", x.ListB), 
        string.Join(", ", x.Shared),
        allLists.IndexOf(x.ListX),
        string.Join(", ", x.ListX), 
        string.Join(", ", x.SingleShared));

I will leave the exercise of further work such as which list matches which other one given your fairly generic requirement. So here, I find those that match 3 other values in a given array, processing all arrays - so there are duplicates here where an A matches a B and a B matches an A for example.

This should give you something you can work from:

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

public class Program
{
    public static void Main()
    {
        Console.WriteLine("Hello World");
        var s = new List<int>();
        List<List<int>> allLists = new List<List<int>>();
        allLists.Add(new List<int>()
        {1, 2, 3, 4});
        allLists.Add(new List<int>()
        {1, 2});
        allLists.Add(new List<int>()
        {3, 4});
        allLists.Add(new List<int>()
        {3, 4, 5, 6, 7, 8, 9});
        allLists.Add(new List<int>()
        {4, 6, 8});
        allLists.Add(new List<int>()
        {5, 7, 9, 11});
        allLists.Add(new List<int>()
        {6, 7, 8});
        /*
        // To iterate over it.
        foreach (List<int> subList in allLists)
        {
            foreach (int item in subList)
            {
                Console.WriteLine(item);
            }
        }
  */
        var countMatch = 3;
        /* iterate over our lists */
        foreach (var sub in allLists)
        {
            /* not the sub list */
            var ns = allLists.Where(g => g != sub);
            Console.WriteLine("Check:{0}", ns.Count()); // 6 of the 7 lists so 6 to check against
            //foreach (var glist in ns) - all of them, now refactor to filter them:
            foreach (var glist in ns.Where(n=> n.Intersect(sub).Count() == countMatch))
            {
                var r = sub.Intersect(glist); // get all the matches of glist and sub
                Console.WriteLine("Matches:{0} in {1}", r.Count(), glist.Count());
                foreach (int item in r)
                {
                    Console.WriteLine(item);
                }
            }
        }
    }
}

This will output this:

Hello World
Check:6
Check:6
Check:6
Check:6
Matches:3 in 3
4
6
8
Matches:3 in 4
5
7
9
Matches:3 in 3
6
7
8
Check:6
Matches:3 in 7
4
6
8
Check:6
Matches:3 in 7
5
7
9
Check:6
Matches:3 in 7
6
7
8

I think it would be better to break this functionality into several methods, then it will look easier to read.

var allLists = new List<List<int>>();
allLists.Add(new List<int>() {1, 2, 3, 4});
allLists.Add(new List<int>() {1, 2});
allLists.Add(new List<int>() {3, 4});
allLists.Add(new List<int>() {3, 4, 5, 6, 7, 8, 9});
allLists.Add(new List<int>() {4, 6, 8});
allLists.Add(new List<int>() {5, 7, 9, 11});
allLists.Add(new List<int>() {6, 7, 8});
var count = allLists.Count;
for (var i = 0; i < count - 1; i++)
{
    var left = allLists[i];
    if (left.Count > 2)
    {
        for (var j = i + 1; j < count; j++)
        {
            var right = allLists[j];
            var sharedItems = left.Intersect(right).ToList();
            if (sharedItems.Count == 3)
            {
                for (int k = 0; k < count; k++)
                {
                    if (k == i || k == j)
                        continue;
                    var intersected = allLists[k].Intersect(sharedItems).ToList();
                    if (intersected.Count == 1)
                    {
                        Console.WriteLine($"Found index k:{k},i:{i},j:{j}, Intersected numbers:{string.Join(",",intersected)}");
                    }
                }
                
            }
        }
    }
}

I just thought if I try to find the item in List X first, I might need fewer loops in practice. Correct me if I am wrong.

        public static void match(List<List<int>> allLists, int numberOfMainListsToExistIn, int numberOfCommonItems)
        {
            var possibilitiesToCheck = allLists.SelectMany(i => i).GroupBy(e => e).Where(e => (e.Count() == numberOfMainListsToExistIn + 1));
            foreach (var pGroup in possibilitiesToCheck)
            {
                int p = pGroup.Key;
                List<int> matchingListIndices = allLists.Select((l, i) => l.Contains(p) ? i : -1).Where(i => i > -1).ToList();

                for (int i = 0; i < matchingListIndices.Count; i++)
                {
                    int aIndex = matchingListIndices[i];
                    int bIndex = matchingListIndices[(i + 1) % matchingListIndices.Count];
                    int indexOfListXIndex = (i - 1 + matchingListIndices.Count) % matchingListIndices.Count;
                    int xIndex = matchingListIndices[indexOfListXIndex];

                    IEnumerable<int> shared = allLists[aIndex].Intersect(allLists[bIndex]).OrderBy(e => e);
                    IEnumerable<int> xSingle = shared.Intersect(allLists[xIndex]);
                    bool conditionsHold = false;
                    if (shared.Count() == numberOfCommonItems && xSingle.Count() == 1 && xSingle.Contains(p))
                    {
                        conditionsHold = true;
                        for (int j = 2; j < matchingListIndices.Count - 1; j++)
                        {
                            int cIndex = matchingListIndices[(i + j) % matchingListIndices.Count];
                            if (!Enumerable.SequenceEqual(shared, allLists[aIndex].Intersect(allLists[cIndex]).OrderBy(e => e)))
                            {
                                conditionsHold = false;
                                break;
                            }

                        }
                        if (conditionsHold)
                        {
                            List<int> theOtherListIndices = Enumerable.Range(0, allLists.Count - 1).Except(matchingListIndices).ToList();
                            if (theOtherListIndices.Any(x => shared.Intersect(allLists[x]).Count() > 0))
                            {
                                conditionsHold = false;
                            }
                        }
                    }
                    if (conditionsHold)
                    {
                        matchingListIndices.RemoveAt(indexOfListXIndex);
                        Console.Write("List A and B: {0}. ", String.Join(", ", matchingListIndices));
                        Console.Write("Common items: {0}. ", String.Join(", ", shared));
                        Console.Write("List X: {0}.", xIndex);
                        Console.WriteLine("Common item in list X: {0}. ", p);
                    }
                }
            }
        }

For the above example, I will just call the method like this:

match(allLists, 2, 3);

This method will also work with the extended problem:

match(allLists, 3, 4);

... and even more if the problem is even further more extended to (4, 5) and so on...