java - 当某些值必须晚于其他值出现时如何对列表进行排序，可能会忽略需要 'delaying' 的此类项目的排序顺序

Question

问题

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

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

一个例子

如果我有元素:

[{'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和< em>h 已按正确顺序排序 b、c、h、e、< em>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)) implies compare(x, z)>0.

然而，在上面的例子中

• a(6) < h(7) : 真
• h(7) < e(12) : 真
• a(6) < e(12) : 错误

相反，我提出了下面的代码，虽然可以运行，但对于看似简单的问题来说，它似乎过于庞大且过于复杂。 (注意:这是一个略微精简的类(class)版本。也可以在 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 实现的与语言无关的答案也很好。

Answer 1

这叫做 topological sorting .您可以将“阻塞”建模为有向图的边。如果没有循环“阻塞”，这应该可以工作。