问题

我需要按列表中每个对象的某个属性对列表进行排序。这是大多数语言支持的标准操作。

但是，还有一项附加要求，即某些项目可能依赖于其他项目，因此，在它们所依赖的项目首先出现之前，不得出现在排序列表中，即使这需要违反正常的排序顺序。任何被“阻止”的此类项目，都应在“阻止”项目添加到输出列表时出现在列表中。

示例

如果我有物品：

[{'a',6},{'b',1},{'c',5},{'d',15},{'e',12},{'f',20},{'g',14},{'h',7}]

按数值正常排序将得到：

[{'b',1},{'c',5},{'a',6},{'h',7},{'e',12},{'g',14},{'d',15},{'f',20}]

但是，如果强制实施以下约束：

• a 取决于 e
• g 取决于 d
• c 取决于 b

则此结果无效。相反，结果应该是：

[{'b',1},{'c',5},{'h',7},{'e',12},{'a',6},{'d',15},{'g',14},{'f',20}]

其中 b、c、d、e、f 和 h 已按正确的顺序排序 b、c、h、e、d 和 f;a 和 g 都被延迟，直到分别输出 e 和 d;c不需要延迟，因为它所依赖的值b已经输出。

我已经尝试过了什么

最初，我研究了使用基本的Java比较器是否可以做到这一点，其中比较器的实现如下所示：

private Map<MyObject,Set<MyObject>> dependencies; // parent to set of children

public int compare(MyObj x, MyObj y) {
   if (dependencies.get(x).contains(y)) {
      return 1;
   } else if (dependencies.get(y).contains(x)) {
      return -1;
   } else if (x.getValue() < y.getValue()) {
     return -1;
   } else if (x.getValue() > y.getValue()) {
     return 1;
   } else {
     return 0;
   }
}

然而，这打破了Java比较器的可传递性要求。摘自 java 文档：

((compare(x, y)>0) && (compare(y, z)>0))意味 着。compare(x, z)>0

但是，在上面的示例中

• a（6） < h（7） ： 真
• h（7） < e（12） ： 真
• a（6） < e（12） ： 假

相反，我想出了下面的代码，虽然可以工作，但对于一个看似简单的问题来说，它似乎非常过大和过于复杂。（注意：这是该类的略微精简版本。它也可以在 https://ideone.com/XrhSeA）查看和运行

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public final class ListManager<ValueType extends Comparable<ValueType>> {
    private static final class ParentChildrenWrapper<ValueType> {
        private final ValueType parent;
        private final Set<ValueType> childrenByReference;

        public ParentChildrenWrapper(ValueType parent, Set<ValueType> childrenByReference) {
            this.parent = parent;
            this.childrenByReference = childrenByReference;
        }

        public ValueType getParent() {
            return this.parent;
        }

        public Set<ValueType> getChildrenByReference() {
            return this.childrenByReference;
        }
    }

    private static final class QueuedItem<ValueType> implements Comparable<QueuedItem<ValueType>> {
        private final ValueType item;
        private final int index;

        public QueuedItem(ValueType item, int index) {
            this.item = item;
            this.index = index;
        }

        public ValueType getItem() {
            return this.item;
        }

        public int getIndex() {
            return this.index;
        }

        @Override
        public int compareTo(QueuedItem<ValueType> other) {
            if (this.index < other.index) {
                return -1;
            } else if (this.index > other.index) {
                return 1;
            } else {
                return 0;
            }
        }
    }

    private final Set<ValueType> unsortedItems;
    private final Map<ValueType, Set<ValueType>> dependentsOfParents;

    public ListManager() {
        this.unsortedItems = new HashSet<>();
        this.dependentsOfParents = new HashMap<>();
    }

    public void addItem(ValueType value) {
        this.unsortedItems.add(value);
    }

    public final void registerDependency(ValueType parent, ValueType child) {
        if (!this.unsortedItems.contains(parent)) {
            throw new IllegalArgumentException("Unrecognized parent");
        } else if (!this.unsortedItems.contains(child)) {
            throw new IllegalArgumentException("Unrecognized child");
        } else if (Objects.equals(parent,child)) {
            throw new IllegalArgumentException("Parent and child are the same");
        } else {
            this.dependentsOfParents.computeIfAbsent(parent, __ -> new HashSet<>()).add(child);
        }
    }

    public List<ValueType> createSortedList() {
        // Create a copy of dependentsOfParents where the sets of children can be modified without impacting the original.
        // These sets will representing the set of children for each parent that are yet to be dealt with, and such sets will shrink as more items are processed.
        Map<ValueType, Set<ValueType>> blockingDependentsOfParents = new HashMap<>(this.dependentsOfParents.size());
        for (Map.Entry<ValueType, Set<ValueType>> parentEntry : this.dependentsOfParents.entrySet()) {
            Set<ValueType> childrenOfParent = parentEntry.getValue();
            if (childrenOfParent != null && !childrenOfParent.isEmpty()) {
                blockingDependentsOfParents.put(parentEntry.getKey(), new HashSet<>(childrenOfParent));
            }
        }

        // Compute a list of which children impact which parents, alongside the set of children belonging to each parent.
        // This will allow a child to remove itself from all of it's parents' lists of blocking children.
        Map<ValueType,List<ParentChildrenWrapper<ValueType>>> childImpacts = new HashMap<>();
        for (Map.Entry<ValueType, Set<ValueType>> entry : blockingDependentsOfParents.entrySet()) {
            ValueType parent = entry.getKey();
            Set<ValueType> childrenForParent = entry.getValue();
            ParentChildrenWrapper<ValueType> childrenForParentWrapped = new ParentChildrenWrapper<>(parent,childrenForParent);
            for (ValueType child : childrenForParent) {
                childImpacts.computeIfAbsent(child, __ -> new LinkedList<>()).add(childrenForParentWrapped);
            }
        }

        // If there are no relationships, the remaining code can be massively optimised.
        boolean hasNoRelationships = blockingDependentsOfParents.isEmpty();

        // Create a pre-sorted stream of items.
        Stream<ValueType> rankedItemStream = this.unsortedItems.stream().sorted();
        List<ValueType> outputList;
        if (hasNoRelationships) {
            // There are no relationships, and as such, the stream is already in a perfectly fine order.
            outputList = rankedItemStream.collect(Collectors.toList());
        } else {
            Iterator<ValueType> rankedIterator = rankedItemStream.iterator();

            int queueIndex = 0;
            outputList = new ArrayList<>(this.unsortedItems.size());

            // A collection of items that have been visited but are blocked by children, stored in map form for easy deletion.
            Map<ValueType,QueuedItem<ValueType>> lockedItems = new HashMap<>();
            // A list of items that have been freed from their blocking children, but have yet to be processed, ordered by order originally encountered.
            PriorityQueue<QueuedItem<ValueType>> freedItems = new PriorityQueue<>();

            while (true) {
                // Grab the earliest-seen item which was once locked but has now been freed. Otherwise, grab the next unseen item.
                ValueType item;
                boolean mustBeUnblocked;
                QueuedItem<ValueType> queuedItem = freedItems.poll();
                if (queuedItem == null) {
                    if (rankedIterator.hasNext()) {
                        item = rankedIterator.next();
                        mustBeUnblocked = false;
                    } else {
                        break;
                    }
                } else {
                    item = queuedItem.getItem();
                    mustBeUnblocked = true;
                }

                // See if this item has any children that are blocking it from being added to the output list.
                Set<ValueType> childrenWaitingUpon = blockingDependentsOfParents.get(item);
                if (childrenWaitingUpon == null || childrenWaitingUpon.isEmpty()) {
                    // There are no children blocking this item, so start removing it from all blocking lists.

                    // Get a list of all parents that is item was blocking, if there are any.
                    List<ParentChildrenWrapper<ValueType>> childImpact = childImpacts.get(item);
                    if (childImpact != null) {
                        // Iterate over all those parents
                        ListIterator<ParentChildrenWrapper<ValueType>> childImpactIterator = childImpact.listIterator();
                        while (childImpactIterator.hasNext()) {
                            // Remove this item from that parent's blocking children.
                            ParentChildrenWrapper<ValueType> wrappedParentImpactedByChild = childImpactIterator.next();
                            Set<ValueType> childrenOfParentImpactedByChild = wrappedParentImpactedByChild.getChildrenByReference();
                            childrenOfParentImpactedByChild.remove(item);

                            // Does this parent no longer have any children blocking it?
                            if (childrenOfParentImpactedByChild.isEmpty()) {
                                // Remove it from the children impacts map, to prevent unnecessary processing of a now empty set in future iterations.
                                childImpactIterator.remove();

                                // If this parent was locked, mark it as now freed.
                                QueuedItem<ValueType> freedQueuedItem = lockedItems.remove(wrappedParentImpactedByChild.getParent());
                                if (freedQueuedItem != null) {
                                    freedItems.add(freedQueuedItem);
                                }
                            }
                        }
                        // If there are no longer any parents at all being blocked by this child, remove it from the map.
                        if (childImpact.isEmpty()) {
                            childImpacts.remove(item);
                        }
                    }
                    outputList.add(item);
                } else if (mustBeUnblocked) {
                    throw new IllegalStateException("Freed item is still blocked. This should not happen.");
                } else {
                    // Mark the item as locked.
                    lockedItems.put(item,new QueuedItem<>(item,queueIndex++));
                }
            }

            // Check that all items were processed successfully. Given there is only one path that will add an item to to the output list without an exception, we can just compare sizes.
            if (outputList.size() != this.unsortedItems.size()) {
                throw new IllegalStateException("Could not complete ordering. Are there recursive chains of items?");
            }
        }
        return outputList;
    }
}

我的问题

是否有已经存在的算法，或者比上述算法短得多的算法，可以完成此操作？

虽然我正在开发的语言是Java，上面的代码是Java的，但我可以在Java中实现的与语言无关的答案也很好。