算法迅速获得了多个链表一个偏序 [英] Algorithm for quickly obtaining a partial ordering over multiple linked lists

问题描述

我有一种情况，如下：

• 在我的 N 的双向链表
• 在每个列表都有一个定点开始和结束
• 在名单都在同一个的开始和结束点（不是必需的，但为了简单起见）
• 在该名单是同质的，并且可以共享项目

• I have n doubly-linked lists
• Each list has a sentinel beginning and end
• The lists all have the same beginning and end node (not required, but for simplicity's sake)
• The lists are homogenous and may share items

我想找到所有的所有节点的偏序的 N 的名单，从开始节点和结束，好了，端节点，使得出现在任何节点 NX 的名单，其中的 X - LT; ñ的，将被分拣相对于所有列表中的其他节点中出现。

I'd like to find a partial ordering of all nodes in all n lists, starting with the beginning node and ending with, well, the end node, such that any node which appears in n-x lists, where x < n, will be sorted with respect to the other nodes in all the lists in which it appears.

使用数组提供的一个例子组列表：

Using arrays to provide an example set of lists:

first  = [a, b,    d,    f,    h, i];
second = [a, b, c,       f, g,    i];
third  = [a,          e, f, g, h, i];

显然，一个可能的答案是[A，B，C，D，E，F，G，H，I]，但另一个受理的订货会是[A，B，D，E，C，F，G ，H，I]。

Obviously, one possible answer would be [a, b, c, d, e, f, g, h, i], but another admissible ordering would be [a, b, d, e, c, f, g, h, i].

我知道有是快速算法来做到这一点，没有任何人记得如何去和它叫什么？我已经有一些缓慢的版本，但我敢肯定的是，在某个地方有克努特是一个远远快的。

I know that there is a fast algorithm to do this, does anybody remember how it goes or what it is called? I already have a few slow versions, but I'm certain that somewhere in Knuth there is a far faster one.

（而且，我可以告诉大家，这不是家庭作业或项目欧拉，我不能让这个任何更为具体。这的是的问题。）

(And, before you ask, this is not for homework or Project Euler, and I cannot make this any more concrete. This is the problem.)

编辑：我比较肯定的偏序被定义仅只要端点都在所有列表的并在相同的位置（开始和结束）。我不会对一个线性时间的搜索来查找这些端点，如果他们不能被发现，那么错误可能被上升那里。

I am relatively sure that the partial ordering is defined only as long as the endpoints are in all of the lists and in the same positions (beginning and end). I would not be against a linear-time search to find those endpoints, and if they can't be found, then an error could be raised there.

推荐答案

看起来非常相似，拓扑排序给我。有几种算法，让你一个拓扑排序状态。一个我特别喜欢的是类似于广度优先搜索。维持两个列表，其中有没有入边，说 l所有节点之一（最初只是在 A 节点） ，其余与偏序节点， F 。现在，步步为营，

Looks very similar to Topological sort to me. There's several algorithms to get you a topologically sorted state. The one I particularly like is similar to a breadth first search. Maintain two lists, one of all nodes which have no in-edges, say L (initially just the a node), the other with the partial ordered nodes, F. Now at every step,

pick a node from `L`, 
do some operations (explained later), 
and move the chosen node to the `F` list. 

在做一些操作步骤，

choose all successors of the source node which have exactly one in-link add them to L.
Remove the link from the source node to all the successors in the previous step 

现在，名单 F 有你所有的节点拓扑排序。我很抱歉可怕的解释，维基链接有很好的图表：）

Now, the list F has all your nodes topologically sorted. I'm sorry about the awful explanation, the wiki link has nice diagrams :)

这篇关于算法迅速获得了多个链表一个偏序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！