neb*_*uch 5 sorting algorithm user-input transitivity
假设我有一个文件在每一行都有一个单行(笑话).我想通过我发现它们多么有趣来对笑话进行排序.我的第一个想法是实现任何排序算法(最好是尽可能少的比较)并让比较算法接受我的输入; 我只是坐在那里,选择它给我的每一对笑话中哪一个更有趣.
有一个问题.我的笑话偏好不是总订单.它缺乏传递性.例如,我可能认为B在呈现它时比A更有趣,并且C比B更有趣,但是当以某种方式呈现A和C时,我发现A比C更有趣.如果">"意味着"比有趣, "这意味着C> B和B> A不不意味着C> A.所有排序算法正确性取决于此.
但它似乎仍然存在应该是排序笑话的列表中,这样的一个在顶部的算法最优先于其他的笑话,和一个在底部至少优于其他的笑话,即使有个别例外.
我不知道如何谷歌这个.有这种偏好排序的算法吗？这里的答案不适用,因为它强制用户的偏好是可传递的.
如果您将您的决策表示为一个有向图，其中每个笑话都是一个节点，每个有向边表示一个笑话比另一个更好，那么您可以通过构建遵循边并恰好访问每个节点一次的路径来检索排序。
这种类型的图称为锦标赛，路径是哈密顿路径。我有个好消息要告诉你，Bub，如果图是强连通的，则证明存在哈密顿量。强连接只是意味着可以从每个节点到达每个节点，遵守边的方向，所以继续添加边直到这是真的。
锦标赛：https : //en.wikipedia.org/wiki/Tournament_(graph_theory)
哈密顿路径：https : //en.wikipedia.org/wiki/Hamiltonian_path