按用户偏好对一组对象进行排序

Question

给定一组不按特定顺序排列的n个对象(本例中为n = 5)：

{
    apple,
    orange,
    banana,
    cherry,
    cabbage
}

我试图给一个用户几个有三个选项的问题，如下：

banana      vs.      cabbage
      (no preference)

在每个问题之后，它将使用不同的选项(没有相同的偏好)提出一个新的问题，有效地收集关于用户偏好的数据。

在几个问题(本例中为6或7个)之后，它将按顺序给出一个排列顺序最高的对象的列表(数组)：

{
    cherry,
    cabbage,
    orange,
    apple,
    banana
}

但是，我不知道这样的算法是如何工作的，也不知道什么时候停止。如果这是个糟糕的问题，我很抱歉，但是我对算法设计还是很陌生的。

我想这并不重要，但我使用的是JavaScript。

好的，四个月后我会再讨论这个问题，因为我想到了一种新的方法来进行排序。

也许，对每一个对象都有一个下级的列表会更有效，这样任何低于一个对象的东西都会比它的上级更低劣。我解释得很厉害，所以这里有一个视觉：

cherry > cabbage
cabbage > banana
cabbage > apple
apple > orange

thus, cherry > cabbage & banana & apple & orange

用旧的方法，用分数：

apple vs. orange
apple vs. banana (e.g. apple wins)
apple vs. cherry (e.g. cherry wins)
apple vs. cabbage
orange vs. banana
orange vs. cherry
orange vs. cabbage
banana vs. cherry
banana vs. cabbage
cherry vs. cabbage

10 questions

新方法将使cherry vs. banana变得多余，因为我们已经知道apple > banana和cherry > apple。我只需要弄清楚怎么对它进行编码。

唯一的问题出现在人类循环逻辑(即a > b > c > a)中，这是一种可能性，但谢天谢地，这不会是我的特定集合的问题。

Answer 1

您可以使用sort

var sorted = "cherry,cabbage,orange,apple,banana".split(",").sort(function(a,b) {
  return prompt([
    "If you prefer " + a + ", enter -1",
    "If you prefer " + b + ", enter 1",
    "If you don't mind , enter 0"
  ].join("\n"));
});

Answer 2

我使用角-js为您的问题编写了一个小jsFiddle (您不需要使用角)。

这样做的目的是将每个元素与其他元素进行比较。一旦将每个元素与其他元素进行比较，您就完成了。在代码中，关注getNext()函数：

$scope.getNext = function(string) {
    if(string == 'one') {
        $scope.foodArray[x].score++;
    } else {
        $scope.foodArray[y].score++;                
    }
    if(y < $scope.foodArray.length -1) {
        y++;
        $scope.foodTwo = $scope.foodArray[y];
    } else if(x < $scope.foodArray.length -2) {
        y = 2 + x;
        x++;
        $scope.foodOne = $scope.foodArray[x];
        $scope.foodTwo = $scope.foodArray[y];
    } else {
        finish();   
    }
}

前两条if语句用于确定获胜者。

正如您所看到的，我使用变量x和y来存储矩阵中的当前位置。首先，我比较食物数0 (= x)和1，2，3，4( =y)。当y到达array.ength-1时，将1加到x，并将y设为x +1。当x到达array.ength-2和y array.ength-1时，意味着，您将所有东西与其他所有事物进行比较。现在您可以按分数对数组进行排序，您就完成了:)

编辑：这是新的小提琴，它增加了回答“无动于衷”的可能性。

还需要考虑一件事:在理论上处理首选项时，有三个公理：一些解释：

1. 完整性:每个对象都可以与其他所有对象进行比较。
2. 反身性:每一个物体至少和它自己一样好。
3. 传递性:如果a>b和b> c，这就意味着a> c。

这些公理必须应用，以便您可以使用效用函数进行计算。

，但在实践中，，特别是第三种，并不适用。你总能找到这样的人:橘子>苹果，苹果>香蕉，还有香蕉>橘子。

在我的小提琴里，我忽略了这些公理，让用户决定他们是否想要完全合乎逻辑。

Answer 3

您不需要将每一项与其他每一项进行比较。这将需要你问用户15个问题来排序5个项目。已经证明，在7项比较中，您可以得到5项的总排序。

您可以使用排序网络来完成这一任务。对于任何N，您都可以创建一系列比较和交换来对项目进行排序。有已知的最优序列来排序多达16个项目。除此之外，还有生成排序网络的算法(参见链接文章中构建排序网络的)。尽管这些网络没有被证明是最优的，但它们可能比通用排序算法更有效。

你的更大的问题，我认为你太容易掩盖，是循环逻辑的真正可能性。当涉及到用户首选项时，传递性通常不成立。