-2

给定一个对的列表，例如

        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。希望这能让我更清楚我想要找到的东西。

4

1 回答 1

0

我使用此函数返回所有链接的完整哈希集，然后遍历所有初始对以提供此函数。我过滤结果以删除重复项，它解决了这个问题。建议来自用户 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;
    }
于 2018-01-23T13:31:31.640 回答