我有多个有序列表。不幸的是,项目的顺序不是简单的字母或数字比较,否则这是微不足道的。所以我所拥有的是这样的:
List #1 List #2 List #3
groundhog groundhog easter
mothersday mayday mothersday
midsummer laborday halloween
christmas
由此我可以推测出土拨鼠< mothersday,但土拨鼠和复活节的关系未知。我保证列表之间的项目顺序是 self 一致的。 (即,无论出现在哪个列表中,复活节总是在万圣节之前)
但是我需要的是一个新的有序列表,它仅代表其他列表中的每个项目一次,从而保留上面所有已知的关系:
groundhog
easter
mayday
mothersday
midsummer
laborday
halloween
christmas
但是,以下列表也是完全有效的:
easter
groundhog
mothersday
mayday
midsummer
laborday
halloween
christmas
我正在寻找一种相当快速的通用算法,我可以用它来以这种方式对 N 个列表进行排序。 (可以使用 C# 代码当然是一个优点,但不是必需的。)
我有一个可行的解决方案,但它的 O(N^2) 和一条甚至只有适度数据集的狗。
最佳答案
您可能想看看topological sorting 。我认为它非常适合您的情况。
关于c# - 多个有序列表归结为一个列表,其中顺序是相对的,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/282252/