algorithm:根据约束对数组中的对象进行排序

Question

我有一千个类型的对象 MyClass

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

对象objectsBehind数组在哪里MyClass,此数组中的任何对象都是1000个原始对象的一部分.

我将它们放在一个数组中并对它们进行排序,使得一个对象出现在数组中比其objectsBehind数组中的对象更高的索引处.例如,索引546处的对象不能在其objectsBehind数组中具有排序数组中索引大于546的任何对象.

我的问题是这个.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每个此类对象的数组中的所有对象之前对对象进行排序,您将使用拓扑排序.

拓扑排序将每次主要迭代"同时"将多个元素放入输出集合中.

这些对象按大属性排序,这样所有大对象首先出现,然后是所有非大对象.您可能希望在此处添加另一个排序条件,以便您可以依赖大对象内部和非大对象内的已知顺序.

基本上,这是拓扑排序的工作原理(我学到的):

1. 首先创建一些数据结构来保存"图形",即.对象之间的所有链接:
   1. 你需要一个包含每个对象的字典,以及它所链接到的所有对象的列表(在你的情况下实际上不需要这个,因为每个对象都在objectsBehind属性中内置了它)
   2. 您需要一个字典,其中包含链接到的每个对象以及指向该对象的链接数量
   3. 你需要一个没有链接的所有对象的哈希集(目前)
2. 相应地填写这些数据结构
   1. 将所有对象放在hashset中(就好像它们根本没有入站链接一样)
   2. 循环遍历所有具有链接的对象,我们将这个对象称为迭代A
   3. 添加对象(具有来自它的链接)及其拥有的所有链接到第一个字典(同样,对象不需要这样)
   4. 通过增加A对象中每个链接的入站链接数来调整第二个字典
   5. 当您增加对象的入站链接数时,从散列集中删除相同的对象(我们现在知道它至少有一个入站链接)
3. 启动一个循环,基本上说"只要我在hashset中有东西",这将查看hashset,它现在包含所有没有入站链接的对象
4. 在每次循环迭代中,首先输出hashset中的所有对象.剩下的就是"先到先得".您想订购这些产品以产生稳定的排序.在您的情况下,我会首先订购所有大型对象,然后是所有非大型对象.
5. 为枚举目的制作哈希集的副本,并清除哈希集,为下一个循环迭代做准备
6. 遍历副本中的所有对象,并为每个对象循环遍历其中的所有出站链接,并为每个链接减少目标上的入站链接数,在第二个字典中
7. 当这样一个数字,即一个对象的入站链接数量在减少后达到零,这意味着不再有任何"实时"链接指向它,所以将它添加到hashset
8. 绕圈(第4点及以后)

如果在第8点和第4点之后,您在散列集中没有对象,但是第二个字典中的对象没有达到零入站链接,则意味着您在图中有循环,即.沿着"物体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] ->