Найти все группы пар с пересечениями C#

Question

Приведен список пар, таких как

        List<int> pair1 = new List<int>() { 1, 3};
        List<int> pair2 = new List<int>() { 1, 2 };
        List<int> pair3 = new List<int>() { 5, 3 };
        List<int> pair4 = new List<int>() { 7, 8 };
        List<int> pair5 = new List<int>() { 8, 11 };
        List<int> pair6 = new List<int>() { 6, 9 };
        List<int> pair7 = new List<int>() { 2, 13 };
        List<int> pair8 = new List<int>() { 13, 16 };

Как я могу найти все союзы, где пары пересекаются?

Вывод должен быть примерно таким:

1,2,3,5,13,16
7,8,11
6,9


// create lists of pairs to sort through
static void links2XML(SQLiteConnection m_dbConnection)
{
    List<int> pair1 = new List<int>() { 1, 3};
    List<int> pair2 = new List<int>() { 1, 2 };
    List<int> pair3 = new List<int>() { 5, 3 };
    List<int> pair4 = new List<int>() { 7, 8 };
    List<int> pair5 = new List<int>() { 8, 11 };
    List<int> pair6 = new List<int>() { 6, 9 };
    List<int> pair7 = new List<int>() { 2, 13 };
    List<int> pair8 = new List<int>() { 13, 16 };
    var pairs = new List<List<int>>();

    pairs.Add(pair1);
    pairs.Add(pair2);
    pairs.Add(pair3);
    pairs.Add(pair4);
    pairs.Add(pair5);
    pairs.Add(pair6);
    pairs.Add(pair7);
    pairs.Add(pair8);

    var output = new List<int>();
    foreach (var pair in pairs)
    {
        foreach (int i in followLinks(pair, pairs))
        {
            Console.Write(i + ",");
        }
        Console.WriteLine();
    }
}

// loop through pairs to find intersections and recursively call function to 
//build full list of all such ints

static List<int> followLinks(List<int> listA, List<List<int>> listB)
{
    var links = listA;
    var listC = listB.ToList();

    bool added = false;
    foreach (var l in listB)
    {
        var result = listA.Intersect(l);
        if (result.Count<int>() > 0)
        {
            links = links.Union<int>(l).ToList();
            listC.Remove(l); // remove pair for recursion after adding
            added = true;
        }
    }
    if (added)
    {
        followLinks(links, listC);  //recursively call function with updated 
    //list of pairs and truncated list of lists of pairs
        return links;
    }
    else return links;
}

Код должен запрашивать списки пар и выходные группы. Я пробовал это несколькими различными способами, и это, кажется, стало ближе всего. Я уверен, что это требует рекурсивного цикла, но выяснить его структуру сейчас просто не имеет смысла.

Чтобы уточнить некоторые вопросы, пары чисел являются случайными, которые я выбрал для этого вопроса. Фактический набор данных будет намного больше и извлечен из базы данных. Однако эта часть не имеет отношения к моему вопросу, и она все равно уже решена. На самом деле, именно эта сортировка доставляет мне неприятности.

Для дальнейшего уточнения, выходные данные найдут список всех целых чисел из каждой пары, которая имела пересечение... для пар 1,2 и 1,3 выходной результат будет 1,2,3. Учитывая пары 1,2 и 3,5, результат будет 1,2 для одного списка и 3,5 для другого. Надеюсь, это прояснит то, что я пытаюсь найти.

Answer 1

Я использовал эту функцию, чтобы вернуть полный хэш-набор всех ссылок, а затем перебрать все исходные пары для подачи этой функции. Я фильтрую результаты, чтобы удалить дубликаты, и это решает проблему. Предложение было от пользователя Sven.

// Follow links to build hashset of all linked tags
    static HashSet<int> followLinks(HashSet<int> testHs, List<HashSet<int>> pairs)
    {
        while (true)
        {
            var tester = new HashSet<int>(testHs);
            bool keepGoing = false;
            foreach (var p in pairs)
            {
                if (testHs.Overlaps(p))
                {
                    testHs.UnionWith(p);
                    keepGoing = true;
                }
            }
            for (int i = pairs.Count - 1; i == 0; i-- )
            {
                if (testHs.Overlaps(pairs[i]))
                {
                    testHs.UnionWith(pairs[i]);
                    keepGoing = true;
                }
            }
                if (!keepGoing) break;
            if (testHs.SetEquals(tester)) break;
        }
        return testHs;
    }