有条件地重组sortedDictionary（unionFind）

Question

我做了一些C＃代码，输出一个SortedDictionary <int index, list<int>values>>其中索引始终以下面的列表<>的最低int开头。这里是输入的简短的例子（实际上输入的是大）：

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

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

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

最初我遇到了问题，使用foreach与sortedDictionary一起工作，同时也减少了字典集大小。我解决了这个问题，现在用我最新的代码给出这个问题描述的更新。它不再使用foreach，现在有些排序问题需要修正，但作为副作用，它变得非常复杂和庞大。我怀疑它是否应该如此复杂，或者可能写得更短，更简单。

每个列表我叫树，哪里是THOE字典中树木 而光标或Ç我使用像从屏幕的数字读出文本的数字。

目前，我把它放在一个小的概念功能代码在控制台的应用程序。只是为了检查一切是否正常。测试非常复杂，因为数字集可以复杂地链接。所以如果你有很多套和很多数字应该被分类的话，它不是直接可见的。因此手动检查代码的有效性和结果也不容易。

虽然我不确定它现在是否确实能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; 
     } 
    } 
}