我有一个排序问题,我很确定没有规范的"答案" - 但可能有许多不同的方法,每个都有利弊.我有兴趣听一些不同的方法.
假设一群人{p_i | i=1,...,M}正在排名他们最喜欢的冰淇淋口味.总的来说有N不同的口味,但是一个人p_i只对n_i << N他或她最熟悉的口味进行排序.我有兴趣将这些子排名组合成各种N口味的合理整体排名.
对于一个具体的情况:我M和N大概1000(巧合),每个n_i都是关于20.你可以假设在人们的口味中有足够的重叠,这样就没有味道完全"孤立".
同样,即使没有一个明确的答案,我也有兴趣听到不同的方法来解决这个问题.谢谢!
解决这个问题的一种方法是构造一个有向循环图，表示元素排序的所有约束。图中的节点将代表要比较的不同元素，如果有人对第一个元素比第二个元素进行了排名，那么您将获得从第一个节点到第二个节点的边。该图不会太大，并且可以通过为每个图创建一个节点来在线性时间内构建。对象，然后根据偏好添加边缘。
该图有两种可能性。首先，如果图表包含循环，则首选项中一定存在冲突，并且无法对元素进行一致的排序。其次，如果图没有循环，则图的任何拓扑排序都将给出元素的整体一致排序，因为每个元素将被放置在传递地位于其之前的所有元素之后。
希望这可以帮助！