条件重组sortedDictionary (unionFind)

Question

我编写了一些C#代码，它输出一个SortedDictionary <int index, list<int>values>>，其中索引总是以下面的list<>的最低int开始。下面是一个简短的输入示例(实际上输入更大)：

index- Values<>
 2   - 2,3,6,7
 3   - 3,5
 5   - 5,7,9
11   - 11,12,12

现在我想在这里做一些重新排序。这些值是链接索引。我希望对它们进行排序，以便将连接的索引分组在一起，而不使用双重索引。这应该会导致输出

 2 - 2,3,5,6,7,9
11 - 11,12

最初，我在使用foreach处理sortedDictionary时遇到问题，同时也减少了字典集的大小。我解决了这个问题，现在用我的最新代码更新了这个问题的描述。它不再使用预见，一些排序问题现在要解决，但作为一个副作用，它变得相当复杂和大。我怀疑它是否应该如此复杂，或者写得更短、更简单。

我所称的每个列表都是树，其中的字典是树和Cursor或c，我用它们从屏幕上逐个读取文本数字。

目前，我把它放在控制台应用程序中的一个小概念函数代码中。只是想看看这一切是否都有效。测试是相当复杂的，因为数字集可以复杂地连接起来。所以，如果你有大量的集合和数字，它们应该如何排序，那么它就不是直接可见的。因此，手动检查代码有效性和结果也不容易。

虽然我还不确定它现在是否真的100%起作用。它的接缝工作比以前更好。但我认为这个代码并不完美，因为我两次在一组树中行走。前排序和最后排序。

            static SortedDictionary<int, List<int>> NewSort(SortedDictionary<int, List<int>> trees)
    {
        bool debugmode = false;
        //pre sort
        List<int> indexTree = new List<int>();
        foreach (KeyValuePair<int, List<int>> tree in trees)
        {
            indexTree.Add(tree.Key);
        }
        for (int i = 0; i < indexTree.Count; i++)
        {
            int cursor = 1;
            List<int> tree = new List<int>();
            int index = indexTree[i];
            tree = trees[index];
            while ((tree !=null)&& (cursor<tree.Count) )
            {
                int c = tree[cursor ];
                if (trees.ContainsKey(c))
                {
                    if (trees[c] != null)
                    {
                        List<int> u = new List<int>();
                        u = trees[c];
                        tree.AddRange(u);
                        tree.Sort();
                        trees[index] = tree;
                        trees[c] = null;
                    }
                }
                cursor++;
            }
        }
        for (int i = trees.Count; i > 0; i--)
        {
            int c = indexTree[i - 1];
            if (trees[c] == null)
            { trees.Remove(indexTree[i - 1]); }
            else
            {
                trees[c] = trees[c].Distinct().ToList();   //removing all duplicates
            }
        }
        indexTree = new List<int>();

        //resort.
        foreach (KeyValuePair<int, List<int>> tree in trees)
        {
            indexTree.Add(tree.Key);
            if(debugmode) Console.WriteLine("* " +DumpIntList(trees[tree.Key]));
        }
        for (int i = (indexTree.Count); i > 0; i--)
        {
            if (debugmode) Console.WriteLine(i.ToString());
            List<int> tree = new List<int>();
            tree = trees[indexTree[i-1]];
            for (int j = 0; j < tree.Count; j++)
            {
                int c = tree[j];
                for (int k = (i - 2); k > 0; k--)
                {
                    List<int> compareTree = new List<int>();
                    compareTree = trees[indexTree[k]];
                    if (compareTree.IndexOf(c) != -1)   // found !
                    {
                        if (debugmode) Console.Write("found " + c.ToString() + " from ");
                        if (debugmode) Console.WriteLine(DumpIntList(tree) + " in (" + DumpIntList(compareTree)+ ")");
                        tree.Remove(c); // or we would create a duplicate
                        compareTree.AddRange(tree);
                        compareTree = compareTree.Distinct().ToList(); //removing doubles again, doubles as side effect of merging
                        compareTree.Sort();
                        trees.Remove(indexTree[i - 1]);
                        trees[indexTree[k]] = compareTree;
                    }
                }
            }
        }
        return trees;
    }

也许我想要做的是让一些人明白，我在这里尝试的是，我试着看看序列是否有重叠的数字，如果是这样的话，将它们合并。其中，每个系列总是排序，并以该系列的最低数目开始。正如我最近发现的，这可能是UnionFind问题的一个版本。这个问题还出现在Blob检测中，并在一组网页中查找哪些网页是相互链接的。(但我的数据是一组奇怪的实验室测量数据)。

困难在于有很多系列，而且可能不清楚它们是否相连。

1-3-4
4-7-9
11-12
would result in 2 series :
1) 1-3-4-7-9
2) 11-12
But after you add series 12-3 then it would all become one series.

更多的测试数据：

 2 - 2,3,5,6,7           // note my data is always ordered like this
 5 - 5,7,9               // dictionary starts with lowest key
11 - 11,12,12,27,30,31   // each list inside a tree key 
22 - 22,27               // is ordered low to high
23 - 23,25               // lowest int, equals the dict key.
28 - 28,30
34 - 34

输出使用上述功能

 2 - 2,3,5,6,7,9
11 - 11,12,22,27,28,30,31
23 - 23,25
34 - 34

所以当代码接缝开始工作的时候，我非常怀疑它的理想代码，我激怒了两次设置的树。所以我想知道是否有更好的解决方案。这也可能是因为代码没有做我希望它做的事情，因为我仍然在测试它。

Answer 1

我缩小了功能的大小，并对其进行了改进。现在对所有的树木来说，这应该是一个单一的刺激。除非有人知道更好的答案，否则我认为这是“答案”。这些代码已经过测试，可以与更大的集合一起工作，而且我也找不到错误。

    static SortedDictionary<int, List<int>> NewSort(SortedDictionary<int, List<int>> trees)
    {
        bool debugmode = false;
        //pre sort
        List<int> indexTree = new List<int>();
        foreach (KeyValuePair<int, List<int>> tree in trees)
        {
            indexTree.Add(tree.Key);
            if(debugmode) Console.WriteLine("* " +DumpIntList(trees[tree.Key]));
        }
        for (int i = (indexTree.Count); i > 0; i--)
        {
            if (debugmode) Console.WriteLine(i.ToString());
            List<int> tree = new List<int>();
            tree = trees[indexTree[i-1]];
            for (int j = 0; j < tree.Count; j++)
            {
                int c = tree[j];
                for (int k = (i - 2); k > -1; k--)      // k can be 0 but i can minimally be 1
                {
                    List<int> compareTree = new List<int>();
                    compareTree = trees[indexTree[k]];  // for loop > checking all trees
                    if (compareTree.IndexOf(c) != -1)   // found !
                    {
                        if (debugmode) Console.Write("found " + c.ToString() + " from ");
                        if (debugmode) Console.WriteLine(DumpIntList(tree) + " in (" + DumpIntList(compareTree)+ ")");
                      //  tree.Remove(c);               // or we would create a duplicate
                        compareTree.AddRange(tree);
                        compareTree = compareTree.Distinct().ToList();

                        compareTree.Sort();
                        trees.Remove(indexTree[i - 1]);
                        trees[indexTree[k]] = compareTree;
                        j =tree.Count;                  //break from more checks. maybe dirty code but it increases speed
                        break;                          //break checking loop on all trees for current tree
                    }
                }
            }
        }
        return trees;
    }

Answer 2

除了反转if以避免1级嵌套之外，我还不知道如何使用LINQ来提高这个代码块的可读性。

        static SortedDictionary<int, List<int>> SortTree(SortedDictionary<int, List<int>> trees)
        {
            //SortedDictionary<int, List<int>> newtrees = new SortedDictionary<int, List<int>>();

            if (trees.Count < 2) { return trees; }  // dont process if ntrees contains 1 or 0 trees

            foreach (KeyValuePair<int, List<int>> singletree in trees)
            {
                int cursor = 1;
                bool nFinish = false;
                List<int> n = singletree.Value;
                if (n.Count <= 1) continue;
                while (nFinish == false)
                {
                    if (trees.ContainsKey(n[cursor]))
                    {
                        List<int> t = trees[n[cursor]];   // think of a screen cursor going over the list table
                        t.AddRange(n);
                        trees.Remove(n[cursor]);
                        n.Sort();
                        trees[singletree.Key] = n;
                    }
                    cursor++;
                    if (cursor != n.Count) continue;
                    nFinish = true;
                }
            }
            return trees;
        }

Answer 3

下面是您的解决方案和test cases

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

namespace Demo
{
    public class Example
    {
        public static void Main()
        {
            SortedDictionary<int, List<int>> tempRepositary = new SortedDictionary<int, List<int>>();

            //test 1
            tempRepositary.Add(2, new List<int>(new[] { 2, 3, 5, 6, 7 }));
            tempRepositary.Add(5, new List<int>(new[] { 5, 7, 9 }));
            tempRepositary.Add(11, new List<int>(new[] { 11, 12, 12, 27, 30, 31 }));
            tempRepositary.Add(22, new List<int>(new[] { 22, 27 }));
            tempRepositary.Add(23, new List<int>(new[] { 23, 25 }));
            tempRepositary.Add(28, new List<int>(new[] { 28, 30 }));
            tempRepositary.Add(34, new List<int>(new[] { 34 }));

            //test 2
            //tempRepositary.Add(2, new List<int>(new[] { 2,3,6,7 }));
            //tempRepositary.Add(3, new List<int>(new[] { 3,5 }));
            //tempRepositary.Add(5, new List<int>(new[] { 5,7,9 }));
            //tempRepositary.Add(11, new List<int>(new[] { 11,12,12 }));

            var refreshOne = SortTree(tempRepositary);    

            foreach (var item in refreshOne)
            {
                Console.Write("Key:" + item.Key + " ");
                Console.WriteLine(string.Join(",", item.Value));                 
            }

            Console.ReadKey();
        }

        private static SortedDictionary<int, List<int>> SortTree(SortedDictionary<int, List<int>> trees)
        {
            if (trees.Count < 2) { return trees; }  // dont process if ntrees contains 1 or 0 trees

            SortedDictionary<int, List<int>> compressedTree
                = new SortedDictionary<int, List<int>>();

            var allKeys = trees.Keys.ToList();
            var allValues = trees.Values.ToList();

            for (int i = 0; i < allKeys.Count; i++)
            {
                var tempValues = allValues[i];
                var tempMax = tempValues.Max();

                for (int j = i + 1; j < allKeys.Count; )
                {
                    if (tempMax >= allKeys[j])
                    {
                        tempValues.AddRange(allValues[j]);
                        allKeys.Remove(allKeys[j]);
                        allValues.Remove(allValues[j]);
                        //
                        tempMax = tempValues.Max();
                        continue;
                    }
                    j++;
                }

                compressedTree.Add(allKeys[i], tempValues.Distinct().OrderBy(i1 => i1).ToList());
            }

            return compressedTree;
        }
    }
}