算法：在數組排序對象基於約束

Question

我有型的一千對象MyClass

class MyClass{ 
    array<MyClass> objectsBehind; 
    Boolean large; 
} 

哪裏objectsBehind是MyClass對象和任何對象的數組中的數組是1000的一部分原始對象。

我把它們放在一個數組中並對它們進行排序，使得一個對象出現在數組中比索引號objectsBehind中的對象更高的索引處。例如，索引爲546的對象的排序數組中的索引大於546的數組的objectsBehind中不能有任何對象。

我的問題是這樣的。 1000個物體中約有20個物業擁有物業large = true。如果不違反objectsBehind屬性，將這些「大」對象按順序分組到排序數組中是有益的。例如，它會更好，有這樣的：

array[45].large = false; array[46].large = true, array[47].large = true, array[48].large = true, array[49].large = false; 

比

array[45].large = true; array[46].large = false, array[47].large = true, array[48].large = false, array[49].large = true; 

在第一序列中，我有三個大的對象組合在一起，而不是讓他們在第二個例子中展開。

我想不出一個好辦法做到這一點。有任何想法嗎？

Answer 1

這可能很容易完成。

首先，要對每個這樣的對象的objectsBehind數組中的所有對象進行排序，可以使用Topological Sort。

拓撲排序將每個主迭代將多個元素同時放置到輸出集合中。

這些您按大屬性排序的對象，以便所有大對象先出現，然後出現所有非大對象。您可能希望在此處添加另一個排序條件，以便您可以依賴大對象內部和非大對象內的已知順序。

基本上，這裏的排序是如何工作的拓撲（一個我已經學會）：

1. 開始通過創建幾個數據結構來保存「圖」，即。所有對象之間的聯繫：
   1. 你需要一個包含每個對象的字典，以及所有它鏈接到的對象的列表（這其實並不需要你的情況，因爲每個對象都有這個建在在objectsBehind屬性）
   2. 你需要在上面放置鏈接到隨着有多少這樣的鏈接指向的對象每個對象字典
   3. 你需要所有具有對象的一個​​HashSet 沒有鏈接到他們（目前）
2. 填充這些數據結構相應
   1. 將所有對象在HashSet的（好像他們有沒有入站鏈接的話）通過所有有聯繫的對象
   2. 循環中，我們將調用這個對象迭代A
   3. 添加對象（包含鏈接）以及它與第一個字典的所有鏈接（同樣，對象不需要）
   4. 通過增加入站鏈接數來調整第二個字典從A對象
   5. 每一個環節如你增加一個對象的入站鏈接數量，從哈希集中刪除同一個對象（我們現在知道它至少有一個入站鏈接）
3. 開始一個循環，基本上說「只要我有東西在HashSet的」，這將看HashSet的，它現在包含了有沒有入站鏈接
4. 在每次循環迭代，第一輸出都在HashSet中的對象的對象。這是「剩下的第一」。你想要訂購這些來產生穩定的排序。在你的情況下，我會先排序所有大對象，然後排序所有非大對象。
5. 製作哈希集的副本，用於枚舉目的並清除哈希集，爲下一次循環迭代做準備
6. 循環遍歷副本中的所有對象以及每個對象，通過它的所有出站鏈接循環，並且對於每個鏈接，減少目標上的入站鏈接的數量，在第二個詞典中
7. 當這樣一個數字（即到對象的入站鏈接的數量）減少後變爲零時，這意味着不再有任何「活的「鏈接指向它，因此將它添加到哈希集
8. 環繞（點4及以上）

如果，8點和4個後，你必須在HashSet中沒有對象，但在第二個字典對象還沒有達到零個的入站鏈接，它意味着你有周期圖中的，即。 「對象1指向對象2，對象2指向3，並且3指向1」。

這裏是一個這樣的解決方案，你可以在LINQPad中測試一下。

請注意，有很多方法可以做到拓撲排序。例如，這裏的這個版本將採用所有沒有對象的對象，並且同時輸出這些對象。然而，你可以將直接在這些對象之後出現的對象分組，直接在對象之後，並且仍然沒有違反任何約束。

舉個例子，在下面的代碼中檢查4和7之間的關係（你必須運行它）。

const int OBJECT_NUM = 10; 

void Main() 
{ 
    Random r = new Random(12345); 
    var objects = new List<MyClass>(); 
    for (int index = 1; index <= OBJECT_NUM; index++) 
    { 
     var mc = new MyClass { Id = index, IsLarge = (r.Next(100) < 50) }; 
     objects.Add(mc); 
    } 
    for (int index = 0; index < objects.Count; index++) 
    { 
     var temp = new List<MyClass>(); 
     for (int index2 = index + 1; index2 < objects.Count; index2++) 
      if (r.Next(100) < 10 && index2 != index) 
       temp.Add(objects[index2]); 
     objects[index].ObjectsBehind = temp.ToArray(); 
    } 

    objects.Select(o => o.ToString()).Dump("unsorted"); 
    objects = LargeTopoSort(objects).ToList(); 
    objects.Select(o => o.ToString()).Dump("sorted"); 
} 

public static IEnumerable<MyClass> LargeTopoSort(IEnumerable<MyClass> input) 
{ 
    var inboundLinkCount = new Dictionary<MyClass, int>(); 
    var inputArray = input.ToArray(); 

    // the hash set initially contains all the objects 
    // after the first loop here, it will only contain objects 
    // that has no inbound links, they basically have no objects 
    // that comes before them, so they are "first" 
    var objectsWithNoInboundLinks = new HashSet<MyClass>(inputArray); 

    foreach (var source in inputArray) 
    { 
     int existingInboundLinkCount; 

     foreach (var target in source.ObjectsBehind) 
     { 
      // now increase the number of inbound links for each target 
      if (!inboundLinkCount.TryGetValue(target, out existingInboundLinkCount)) 
       existingInboundLinkCount = 0; 
      existingInboundLinkCount += 1; 
      inboundLinkCount[target] = existingInboundLinkCount; 

      // and remove it from the hash set since it now has at least 1 inbound link 
      objectsWithNoInboundLinks.Remove(target); 
     } 
    } 

    while (objectsWithNoInboundLinks.Count > 0) 
    { 
     // all the objects in the hash set can now be dumped to the output 
     // collection "at the same time", but let's order them first 

     var orderedObjects = 
      (from mc in objectsWithNoInboundLinks 
      orderby mc.IsLarge descending, mc.Id 
      select mc).ToArray(); 

     foreach (var mc in orderedObjects) 
      yield return mc; 

     // prepare for next "block" by clearing the hash set 
     // and removing all links from the objects we just output 
     objectsWithNoInboundLinks.Clear(); 

     foreach (var source in orderedObjects) 
     { 
      foreach (var target in source.ObjectsBehind) 
      { 
       if (--inboundLinkCount[target] == 0) 
       { 
        // we removed the last inbound link to an object 
        // so add it to the hash set so that we can output it 
        objectsWithNoInboundLinks.Add(target); 
       } 
      } 
     } 
    } 
} 

public class MyClass 
{ 
    public int Id; // for debugging in this example 
    public MyClass[] ObjectsBehind; 
    public bool IsLarge; 

    public override string ToString() 
    { 
     return string.Format("{0} [{1}] -> {2}", Id, IsLarge ? "LARGE" : "small", string.Join(", ", ObjectsBehind.Select(o => o.Id))); 
    } 
} 

輸出：

unsorted 
1 [LARGE] -> 5 
2 [LARGE] -> 
3 [small] -> 
4 [small] -> 7 
5 [small] -> 
6 [small] -> 
7 [LARGE] -> 
8 [small] -> 
9 [LARGE] -> 10 
10 [small] -> 


sorted 
1 [LARGE] -> 5 
2 [LARGE] -> 
9 [LARGE] -> 10 
3 [small] -> 
4 [small] -> 7 
6 [small] -> 
8 [small] -> 
7 [LARGE] -> 
5 [small] -> 
10 [small] ->