以1比1的选择协作排序算法 [英] Collaborative sorting algorithm based on 1 vs 1 choice

问题描述

我不知道这是一种更数学对象，但我潜藏着mathexchange，不看算法为本所以preFER在这里问。

I don't know if this is a more mathematical object, but I lurked mathexchange and doesn't look algorithm oriented so I prefer to ask here.

我想知道，如果下面的问题，就解决了：

I would like to know if the following problem, was already resolved:

让我们说我们有10个对象，我们打算对它们进行排序基于preferences。如果排序属于一个人，没问题，我们请他来回答我们的问题（使用冒泡或类似），并回答，一大堆的问题后，他将获得最终排名。

let's say we have 10 objects and that we want to sort them preferences based. If the sort pertains a single person, no problem, we ask him to answer to our questions (using bubblesort or similar) and answering, after a bunch of questions, he will receive the final ranking.

现在，让我们说，有10人。我们要建立一个全球性排名。它变得困难，任何人都可以有它的方式来解决问题（例如，要求第一最喜欢的三给大家，并指派点，然后进行排名）;

Now let's say that there are 10 persons. And we want to make a global rank. It becomes difficult, and anyone can have its way to solve the problem (for example, asking for the "first favourite three" to everyone and assigning points, then make a ranking);

我想是更科学，因此更算法，所以，换句话说，使用冒泡排序（它的实现，就像是一系列的问题1VS1对象，并询问什么是你最喜欢的，然后进行排名）为十人，最小化的问题要问。

I would like to be more scientific and therefore more algorithmic, so, in other words, use bubble sort (whose implementation, is like a series of question 1vs1 objects and asking what's your favourite, then make a ranking) for the ten people, minimizing the questions to ask.

因此​​，我们应该有一种方法来全球排名的对象，并在同时指派的人谁都会进行排序，非常重要，如果可能的话，不要等到anyoone使得他的排名，但是，百分比和统计的基础。

So we should have a way to global rank the objects, and in the meanwhile assigning to the people who will sort, major importance, and if possible, don't wait for anyoone making his ranking but on percentages and statistics basis.

希望有很好地解释我的问题，请你不觉得这是这个群体，让我知道和转让的其他服务。谢谢！

Hope to have explained well my question, please if you don't feel it's for this group, let me know and transfer on another service. Thanks!

推荐答案

您的问题是对的阿罗定理。总之，你正在做什么是不可能的了一般。

You question is the subject of Arrow's Theorem. In short, what you are trying to do is impossible in general.

如果你仍然想尝试，我建议用有向边有向图重新present preferences;像大多数prefers A到B，包括边A-> B，并在案件的关系没有优势。如果结果是一个有向无环图，恭喜你，你可以订购一个toposort的项目。否则，使用的Tarjan的算法来识别强连接组件，它们是麻烦点。

If you still want to try, I suggest using directed edges in a directed graph to represent preferences; something like majority prefers A to B, include edge A->B, and no edge in case of ties. If the result is a Directed Acyclic Graph, congratulations, you can order the items with a toposort. Otherwise use Tarjan's Algorithm to identify strongly connected components, which are the trouble spots.

在一般情况下，最好的出路这一难题在我看来是为了获得分数，而不是排名项目配对。然后你只需平均分数。

In general, the best way out of this conundrum in my opinion is to obtain scores rather than ranking pairs of items. Then you just average the scores.

这篇关于以1比1的选择协作排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！