说我有一个整数列表，其中每个元素是一个数字，从1到20。（这不是我想要进行排序。）

Say I have a list of integers, where each element is a number from 1 to 20. (That's not what I'm trying to sort.)

现在，我有业务，其中的每个操作的数组：

Now, I have an array of "operations", where each operation:

的删除的从列表中某些（已知）号 和 添加的某些其他（已知）号码列表 和无法处理列表中是否含有一定的（已知）的数字在操作开始 - 调用这些的 prevent 的 Removes certain (known) numbers from the list and Adds certain other (known) numbers to the list and Is unable to handle the list if it contains certain (known) numbers at the beginning of the operation - call these Prevent

编辑：有可能在每个零个或多个数字的添加的删除和 prevent 的每一个操作，每个数字可以在每个组对一些操作中出现零或更多次。对于任何给定的操作，添加和删除的是不相交的， prevent 和删除的是不相交的，但添加和 prevent 的可能重叠。

There can be zero or more numbers in each of Adds, Removes, and Prevent for each operation, and each number can appear zero or more times in each group for some operation. For any given operation, Adds and Removes are disjoint, Prevent and Removes are disjoint, but Adds and Prevent may overlap.

我要操作的数组进行排序，使每个操作：

I want to sort the array of operations so that for each operation:

如果该操作已 prevent 的物品，它被放置了的动作后除去的那些数字。如果没有后立即，不可能有一个的添加的操作，增加了这些数字后面的最后一个之间的移除的和的 prevent 的 如果操作的删除的项目，那的所有的操作添加的任何这些项目被摆在它面前。 If the operation has Prevent items, it is placed after an operation that Removes those numbers. If not immediately after, there cannot be an Adds operation that adds those numbers back between the last Removes and the Prevent. If the operation Removes items, all operations that Adds any of those items is placed before it.

在循环依赖的情况下，运营的连锁应删除尽可能多的数字尽可能和告诉我，它不能消除所有的数字。

In the event of a circular dependency, the chain of operations should remove as many numbers as possible and inform me that it could not remove all the numbers.

有一个名称/实现此类算法胜过了一个我下面？

补充8/23：赏金是覆盖排序要求同时考虑运codeS（组结构）和 InstructionSemantics （组从枚举位标志）。

Added 8/23: The bounty is for covering the sort requirements considering both the OpCodes (set of structs) and InstructionSemantics (set of bit flags from an enumeration).

后8/23补充：通过启发式pre-排序源阵列1性能改进：我做了89。请参阅我的详细信息，目前的答案。

Added later 8/23: I made an 89:1 performance improvement by heuristically pre-sorting the source array. See my current answer for details.

namespace Pimp.Vmx.Compiler.Transforms
{
    using System;
    using System.Collections.Generic;
    using System.Reflection.Emit;

    internal interface ITransform
    {
        IEnumerable<OpCode> RemovedOpCodes { get; }
        IEnumerable<OpCode> InsertedOpCodes { get; }
        IEnumerable<OpCode> PreventOpCodes { get; }

        InstructionSemantics RemovedSemantics { get; }
        InstructionSemantics InsertedSemantics { get; }
        InstructionSemantics PreventSemantics { get; }
    }

    [Flags]
    internal enum InstructionSemantics
    {
        None,
        ReadBarrier = 1 << 0,
        WriteBarrier = 1 << 1,
        BoundsCheck = 1 << 2,
        NullCheck = 1 << 3,
        DivideByZeroCheck = 1 << 4,
        AlignmentCheck = 1 << 5,
        ArrayElementTypeCheck = 1 << 6,
    }

    internal class ExampleUtilityClass
    {
        public static ITransform[] SortTransforms(ITransform[] transforms)
        {
            throw new MissingMethodException("Gotta do something about this...");
        }
    }
}

编辑：下面这行的背景资​​料什么我其实在做，如果人们想知道为什么我问这个。它不会改变的问题，只是显示的范围。

Below this line is background info on what I'm actually doing, in case people are wondering why I'm asking this. It doesn't change the problem, just shows the scope.

我有一个系统，它读取的项目的列表，并将其发送到另一个模块进行处理。每个项目都是在我的中间再presentation的指令编译器 - 基本上是从1到〜300加17可改性剂（标志枚举）的组合。该处理系统（机器code和汇编）的复杂程度成正比，可能唯一的输入（数字+标志），在那里我有手工code每一个处理器的数量。最重要的是，我必须写至少有3个独立的处理系统（X86，X64，ARM） - 实际处理code的量，我可以使用多个处理系统是最小的。

I have a system that reads in a list of items and sends it to another "module" for processing. Each item is an instruction in my intermediate representation in a compiler - basically a number from 1 to ~300 plus some combination of about 17 available modifiers (flags enumeration). The complexity of the processing system (machine code assembler) is proportional to the number of possible unique inputs (number+flags), where I have to hand-code every single handler. On top of that, I have to write at least 3 independent processing systems (X86, X64, ARM) - the amount of actual processing code I can use for multiple processing systems is minimal.

通过阅读和处理之间插入行动，我可以确保某些项目不会出现加工 - 我做到这一点，当然pressing数字和/或标志在其他的数字。我可以$ C c在一个黑盒子每个转换操作$通过描述它的作用，它为我节省了一吨每个操作的复杂性。该操作是复杂的和唯一的每个变换，但更容易比对处理系统。要拿出多少时间这节省了，我的操作之一写在约6个号码方面预期效果（不带标志）完全删除6的标志。

By inserting "operations" between reading and processing, I can ensure that certain items never appear for processing - I do this by expressing the numbers and/or flags in terms of other numbers. I can code each "transformation operation" in a black box by describing its effects, which saves me a ton of complexity per-operation. The operations are complex and unique for each transformation, but much easier than the processing system is. To show how much time this saves, one of my operations completely removes 6 of the flags by writing their desired effects in terms of about 6 numbers (without flags).

为了让事情在黑盒子，我希望有一个排序算法采取一切我写的操作，责令其产生最大的影响，并通知我，我是如何成功的是简化，最终将达到数据所述处理系统（S）。当然，我针对最复杂的项目，在中间再presentation，并将其简化为基本指针运算在可能的情况，这是最容易处理的装配。 ：）

In order to keep things in the black box, I want an ordering algorithm to take all the operations I write, order them to have the greatest impact, and inform me about how successful I was at simplifying the data that will eventually reach the processing system(s). Naturally, I'm targeting the most complex items in the intermediate representation and simplifying them to basic pointer arithmetic where possible, which is the easiest to handle in the assemblers. :)

与所有的说，我会添加其他笔记。该操作的效果被称为属性效果以上的指令的列表。在一般的业务表现良好，但其中一些仅删除其他号码后回落（如删除不遵循16全部6的）数字。其他人去除包含某些标志的特定号码的所有实例。我将在稍后处理这些 - 后，我找出了保证添加的基本问题/删除/ $上面所列p $ pvent

With all that said, I'll add another note. The operation effects are described as "attribute effects" over the list of instructions. In general the operations behave well, but some of them only remove numbers that fall after other numbers (like remove all 6's that don't follow a 16). Others remove all instances of a particular number that contains certain flags. I'll be handling these later - AFTER I figure out the basic problem of guaranteed add/remove/prevent listed above.

补充8/23： 在这个图片，你可以看到一个通话指令（灰色），其具有 InstructionSemantics.NullCheck 被处理由 RemoveNullReferenceChecks 变换去除语义标记，以换取加入另一个呼叫（没有​​连接到添加的呼叫或者语义）。现在，汇编并不需要了解/手柄 InstructionSemantics.NullCheck ，因为它永远不会看到它们。没有批评ARM code - it's一个占位符，现在的。

Added 8/23: In this image, you can see a call instruction (gray) that had InstructionSemantics.NullCheck was processed by the RemoveNullReferenceChecks transform to remove the semantics flag in exchange for adding another call (with no semantics attached to the added call either). Now the assembler doesn't need to understand/handle InstructionSemantics.NullCheck, because it will never see them. No criticizing the ARM code - it's a placeholder for now.

推荐答案

这适用于现在。 当且仅当的排序存在满足条件，就会发现它。我还没有尝试优化它。它通过跟踪哪些件不允许由previous操作被添加工作在反向

This works for now. If and only if an ordering exists to meet the conditions, it will find it. I haven't tried optimizing it yet. It works in reverse by keeping track of which items are not allowed to be added by the previous operation.

编辑：我不能标记这是一个答案，因为我已经采取了巨大的性能损失，从它，我只有17操作（ ITransform S）。这需要15秒来排序，现在笑/失败。

I can't mark this as an answer because I'm already taking a huge performance hit from it and I only have 17 operations (ITransforms). It takes 15s to sort right now lol/fail.

补充8/23：检查我是如何提高的那种东西，实际上是可行再次下一个code部分

Added 8/23: Check the next code section for how I improved the sort to something that is actually workable once again.

修改8/25：事情变得肮脏再为我穿越25个项目，但事实证明，我不得不在$ p $一个小问题对那种现在是固定的。

Edit 8/25: Things got nasty again as I crossed 25 items, but it turned out I had a small problem in the pre-sort that's fixed now.

    private static ITransform[] OrderTransforms(ITransform[] source)
    {
        return OrderTransforms(
            new List<ITransform>(source),
            new Stack<ITransform>(),
            new HashSet<OpCode>(source.SelectMany(transform => transform.RemovedOpCodes)),
            source.Aggregate(InstructionSemantics.None, (preventedSemantics, transform) => preventedSemantics | transform.RemovedSemantics)
            );
    }

    private static ITransform[] OrderTransforms(List<ITransform> source, Stack<ITransform> selected, HashSet<OpCode> preventAdd, InstructionSemantics preventSemantics)
    {
        if (source.Count == 0 && preventAdd.Count == 0)
            return selected.ToArray();

        for (int i = source.Count - 1; i >= 0; i--)
        {
            var transform = source[i];
            if ((preventSemantics & transform.InsertedSemantics) != 0)
                continue;

            if (preventAdd.Intersect(transform.InsertedOpCodes).Any())
                continue;

            selected.Push(transform);
            source.RemoveAt(i);
#if true
            var result = OrderTransforms(source, selected, new HashSet<OpCode>(preventAdd.Except(transform.RemovedOpCodes).Union(transform.PreventOpCodes)), (preventSemantics & ~transform.RemovedSemantics) | transform.PreventSemantics);
#else // this is even slower:
            OpCode[] toggle = preventAdd.Intersect(transform.RemovedOpCodes).Union(transform.PreventOpCodes.Except(preventAdd)).ToArray();
            preventAdd.SymmetricExceptWith(toggle);
            var result = OrderTransforms(source, selected, preventAdd, (preventSemantics & ~transform.RemovedSemantics) | transform.PreventSemantics);
            preventAdd.SymmetricExceptWith(toggle);
#endif
            if (result != null)
                return result;

            source.Insert(i, transform);
            selected.Pop();
        }

        return null;
    }

在努力收回我的奖金，我从15380s排序时间启发式preconditioning阵列降低到173ms，紧接着上的排序路由。

In an effort to reclaim my bounty, I have reduced the sort time from 15380s to 173ms by heuristically preconditioning the array, immediately followed by the sort routing above.

private static ITransform[] PreSortTransforms(ITransform[] source)
{
    // maps an opcode to the set of transforms that remove it
    ILookup<OpCode, ITransform> removals =
        source
        .SelectMany(transform => transform.RemovedOpCodes.Select(opcode => new
        {
            OpCode = opcode,
            Transform = transform
        }))
        .ToLookup(item => item.OpCode, item => item.Transform);

    // maps an opcode to the set of transforms that add it
    ILookup<OpCode, ITransform> additions =
        source
        .SelectMany(transform => transform.InsertedOpCodes.Select(opcode => new
        {
            OpCode = opcode,
            Transform = transform
        }))
        .ToLookup(item => item.OpCode, item => item.Transform);

    // maps a set of items (A) to a set of items (B), where ALL elements of B must come before SOME element of A
    ILookup<IEnumerable<ITransform>, ITransform> weakForwardDependencies =
        removals
        .SelectMany(item => additions[item.Key].Select(dependency => new
        {
            Transform = item,
            Dependency = dependency
        }))
        .ToLookup(item => item.Transform.AsEnumerable(), item => item.Dependency);

    /* For items in the previous map where set A only had one element, "somewhat" order the
     * elements of set B before it. The order doesn't [necessarily] hold when a key from one
     * relationship is a member of the values of another relationship.
     */
    var ordered =
        weakForwardDependencies
        .Where(dependencyMap => dependencyMap.Key.SingleOrDefault() != null)
        .SelectMany(dependencyMap => dependencyMap.AsEnumerable());

    // Add the remaining transforms from the original array before the semi-sorted ones.
    ITransform[] semiSorted = source.Except(ordered).Union(ordered).ToArray();

    return semiSorted;
}