算法：在数组排序对象基于约束

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] ->