合并多个，任意排序的列表到一个列表 [英] Merging multiple, arbitrarily sorted lists into one list
问题描述
鉴于3列出了由相同但未知的排序顺序任意排序。是否有一个算法，合并这些列表到一个，然后仍然以相同的顺序排序？
例如：
List1的： 一个 b C F ^ h
列表2： b C Ë ^ h
项目list3： C ð Ë ˚F
假设这些列表进行排序，但使用的排序顺序是不知道。我想这些清单结合起来，因此不包含重复，但仍保持了排序顺序： 一个 b C ð Ë F ^ h
正如上面所说：众所周知，在给定列表进行排序，但它不是由哪个顺序已知，但要求是，合并后的列表仍用相同的（未知）顺序进行排序
在上面的例子中，我知道元素f被定位E和H之间，因为从List1中我知道，
C＆LT; F＆LT;为h
从列表2我知道，
C＆LT; E＆LT; h的
和从项目list3我知道
E＆LT; F和c＆所述; E
结合到：
C＆LT; E＆LT; F＆LT; h的
如果排序顺序不能由任何给定的列表来确定，则允许只追加元件到结果列表的末尾。此外，如果一个元素序列的排列顺序不能确定它是允许的，只要它们是在正确的地方（例如，如果我知道，B和C必须插入按任意顺序进榜一个和d之间插入，但我不知道这是否应该是ABCD或ACBD，那么两者都是允许的。）
当然，这仅仅是一个例子。真正的名单是更长的（但含有低于100元），包含不单一的，而是多重的性格元素和排序顺序不是字母。另外，我有多达5个名单。
我需要实现这个算法在Delphi（没有：这不是作业，但现实生活中的问题），但我需要在语言中的算法，只要它不包含太多的编译器魔法或复杂的库函数
性能没有太大的问题，因为这样做一次。
您输入列表定义你的项的偏序的。据在Math.SE 一个答案，你想要的是一个的拓扑排序的。 算法是在维基百科中描述。
Given 3 lists which are arbitrarily sorted by the same but unknown sort order. Is there an algorithm that merges these lists into one which is then still sorted by the same order?
Example:
List1: a b c f h
List2: b c e h
List3: c d e f
Assume these lists are sorted but the sort order used is not known. I want to combine these lists to a result that does not contain duplicates but still maintains the sort order: a b c d e f h
As said above: It is known, that the given lists are sorted but it is not known by which order, but the requirement is that the merged list is still sorted by the same (unknown) order.
In the example above, I know that the element "f" is positioned between "e" and "h" because from List1 I know that
"c" < "f" < "h",
from List2 I know that
"c" < "e" < "h"
and from List3 I know that
"e" < "f" and "c" < "e"
which combines to:
"c" < "e" < "f" < "h"
If the sort order cannot be determined by any of the given lists, it is permissible to just append the element to the end of the result list. Also, if the sort order of a sequence of elements cannot be determined it is permissible to insert them in any order into the list as long as they are in the right place (e.g. if I know that "b" and "c" must be inserted between "a" and "d" but I don't know if it should be a b c d or a c b d, then both are permissible.)
Of course this is just an example. The real lists are longer (but contain less than 100 elements), contain not single but multiple character elements and the sort order is not alphabetic. Also, I have got up to 5 lists.
I need to implement this algorithm in Delphi (and no: This is not homework but a real life problem), but I take an algorithm in an language provided it does not contain too much compiler magic or complex library functions.
Performance is not much of an issue because this is done once.
Your input lists define a partial order of your items. According to an answer at Math.SE, what you want is a topological sort. Algorithms are described on Wikipedia.
这篇关于合并多个，任意排序的列表到一个列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
