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

Question

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

15

给定一个无序的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

由于我们已经知道苹果>香蕉和樱桃>苹果，所以新方法会使得樱桃 vs. 香蕉变得多余。我只需要想出如何编写代码。

唯一的问题是人类循环逻辑（例如a > b > c > a），这可能是一个问题，但幸运的是，在我的特定情况下不会出现这个问题。

- Poyo

3

当涉及到用户偏好时，你的问题可能存在数学问题。有序列表需要一个部分有序关系：http://en.wikipedia.org/wiki/Partially_ordered_set。想象一种情境，当用户在不同的问题中更喜欢苹果胜过橘子、橘子胜过樱桃、樱桃胜过苹果。 - Mehdi

“新的排序方法”只是一种排序。如果元素有良好定义的顺序，可以在O(n logn)的时间复杂度内对它们进行排序。如果您有类似a≤b≤a这样的东西，则≤不是一个偏序，因为它没有传递性。仍然可以使用O(n²)的成本为每对a、b定义a≤b。 - Oriol

10个回答

4

您可以使用 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"));
});

- Oriol

1

当涉及到用户偏好时，您的问题可能存在数学问题。有序列表需要一个部分有序关系：https://en.wikipedia.org/wiki/Partially_ordered_set。想象一种情况，当用户在不同的问题中更喜欢“苹果比橙子好”，“橙子比樱桃好”和“樱桃比苹果好”时。 - Mehdi

1

@Mehdi 没错，用户应该提供一致的答案，否则结果将是未定义的。但是，比较函数应该被尽可能少地调用，所以如果浏览器已经知道cherry vs apple的结果，它们可能不会询问。 - Oriol

1

@Oriol，你需要执行我下面答案中的第三步来优化用户提示的数量。例如，假设用户提到了香蕉<樱桃，后来我们提示并理解苹果<香蕉，我们就不应该再次询问用户苹果和樱桃之间的关系。根据你的排序算法，这可能会被要求，你应该防止这种情况发生。 - user1952500

1

我认为食物口味是一个很好的例子，当从a > b和b > c得出a > c的结论时，这个结论真的是错误的。只需进行测试并回答所有问题，您就会注意到人类不是100％逻辑的。但是，如果问题旨在获取数据以定义特定的理论效用函数，我完全同意您必须强制传递性。 - Andreas Grünh

@AndreasGrünh，如果是这样的话，用户可能需要回答O(n^2)个提示。 - user1952500

我想我把评论放错了帖子！我会把它放在主要问题中。 - Mehdi

1

我为您的问题编写了一个小的jsFiddle，使用angular-js（您不需要使用angular）。

思路是将每个元素与每个其他元素进行比较。一旦每个元素都与每个其他元素进行比较，您就完成了。在代码中，重点关注 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.length-1时，您将向x添加1并将y设置为x + 1。当x达到array.length-2且y array.length-1时，这意味着您已将所有内容与其他内容进行了比较。现在，您可以按得分对数组进行排序，然后完成：）

编辑：这里是新的Fiddle，它增加了以“无所谓”回答的可能性。

还有一件事情需要考虑：在理论上处理偏好时，有三个公理Some explanation：

完备性：每个对象都可以与其他任何对象进行比较
自反性：每个对象至少和它自己一样好
传递性：如果a > b并且b > c，则必须意味着a > c。

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

但在实践中特别是第三个不适用。你总会找到人们说：橙子>苹果，苹果>香蕉但也有香蕉>橙子

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

- Andreas Grünh

这绝对是目前为止最好的答案，但它没有考虑没有偏好的可能性。不断地输入“无偏好”应该导致每个对象具有相同的分数，而不是永远继续算法。 - Poyo

1

我将在10分钟内调整这个fiddle，但你只需要添加一个“无所谓”的按钮，不要增加分数。算法已经完成，当每个比较都完成后，它不关心决策。 - Andreas Grünh

1

您不需要将每个项目与其他项目进行比较。这将要求您向用户提出15个问题来对5个项目进行排序。已经证明，您可以在7次比较中获得5个项目的完全排序。

您可以通过排序网络来实现。对于任何N，您都可以创建一系列比较和交换来对项目进行排序。已知最优序列可用于排序高达16个项目。超过这个范围，有算法可以生成排序网络（请参见链接文章中的构建排序网络）。尽管这些网络未被证明是最优的，但它们可能比通用排序算法更有效率。

我认为您轻描淡写了一个更大的问题，那就是循环逻辑的非常真实的可能性。当涉及到用户偏好时，传递性通常并不成立。

- Jim Mischel

那就是为什么我四个月后进行了编辑。我意识到某些对手会使其他问题完全无效（当然，忽略循环逻辑）。我真的只需要找到一种递归循环遍历所有“下级”的方法。 - Poyo

一个排序网络似乎是可行的方法，但尝试使用值（或一系列值）对它们进行标记以帮助解决循环逻辑问题似乎也很有用。不过，根据您想要的排序精度，标记过程可能会相当棘手。 - Nuclearman

1

“已经证明，在9次比较中可以获得5个项目的完全排序”，难道不是7吗？http://cs.stackexchange.com/a/44982/53177 - AXO

@AXO：是的，那应该是7。不知道我怎么会打成9。感谢您的纠正。 - Jim Mischel

0

你可以根据用户的答案为每个项目添加权重。例如，在你的例子中

banana      vs.      cabbage
      (no preference)

当用户选择香蕉时，您将香蕉项目加一。如果他们选择卷心菜，则给卷心菜加一，然后如果他们选择无偏好，则可以不给任何一个加一。然后您可以将列表从最大值排序到最小值。

- trinityalps

你需要对索引进行一些非常复杂的重新排列。例如，香蕉 < 卷心菜，而且香蕉 < 樱桃 < 橙子 < 卷心菜。因此，基本上香蕉应该比卷心菜少至少3个单位。 - user1952500

2

很遗憾，这并不完全正确。投票结果（香蕉 < 卷心菜），（橙子 < 卷心菜），（香蕉 < 樱桃），（樱桃 < 橙子）将导致得分为：[香蕉(0)，樱桃(1)，橙子(1)，卷心菜(2)]，也就是说你的算法没有清楚地表明橙子比樱桃评分更高。根据所使用的排序算法，它可能会给出错误的结果。 - Bastian Voigt

0

将您的元素存储在这样的数组中：

var preferences = [
  {
    "name": "banana",
    "predecessors": []
  },
  {
    "name": "orange",
    "predecessors": []
  },
  {
    "name": "cabbage",
    "predecessors": []
  },
];

现在根据用户的偏好将前置元素添加到元素中。比如说，一个用户对香蕉比橙子更喜欢，对卷心菜比橙子更喜欢，对卷心菜比香蕉更喜欢。结果：

var preferences = [
  {
    "name": "banana",
    "predecessors": ["orange"]
  },
  {
    "name": "orange",
    "predecessors": []
  },
  {
    "name": "cabbage",
    "predecessors": ["orange", "banana"]
  },
];

现在使用自定义比较函数对数组进行排序：

preferences.sort(function(a,b) {
  if(b.predecessors.contains(a.name)) {
    return -1;
  } 
  if(a.predecessors.contains(b.name)) {
    return 1;
  }
  return 0;
});

请注意，JavaScript没有原生的数组"contains"函数。您可以使用jQuery的$.inArray或underscore的_.contains，或者自己编写一个函数。

- Bastian Voigt

0

使用一个映射（JavaScript 对象可以扮演这个角色），以对象为键，整数（对于所有对象最初设置为 0）为值。

对于每个问题，您都会增加相应选择键的值。由于没有任何偏好影响它们中的任何一个，因此在选择时不需要进行任何操作。

然后迭代映射，找到具有最高值的键值对。返回键即可。

- LeleDumbo

这个问题在于每个键可能没有偶数个问题的可能性。如果您愿意，它不是“轮流进行”的。这样做既不必要，也不适用于更大量的键（即15个以上）。 - Poyo

0

将所有项目保存在一个数组中。使用单独的数组/哈希映射来处理对之间的关系。然后使用您喜欢的基于比较的搜索算法（例如快速排序）。
当要比较两个元素时，使用映射找出相对优先级。如果没有已知的优先级，请询问用户。
添加新的优先级时，调整整个矩阵的优先级顺序。例如，当用户说苹果＜香蕉，然后分别说香蕉＜樱桃时，将苹果＜樱桃添加到哈希映射中。

基于比较的搜索算法旨在优化比较次数，这在本例中转化为优化向用户提问的次数。

- user1952500

0

简单明了：

    var options = {
      A: 0,
      B: 0,
      C: 0,
      D: 0
    };
    var optionsNames = Object.keys(options);

    var results = document.getElementById('results');
    function printResults() {
      var res = optionsNames.map(function(option) {
        return option + ': ' + options[option];
      });
      
      results.innerHTML = res.join('<br>');
    }
    
    function getNextQuestion() {
      var unclear = [];
      optionsNames.sort(function(a, b) {
        if (options[a] == options[b]) unclear.push([a, b]);
        else return options[b] - options[a];
        return 0;
      });
    
      return unclear[0];
    }

    var next;
    function choose(nextIdx) {
      if (next && next[nextIdx] && options[next[nextIdx]] !== undefined) {
        options[next[nextIdx]] += 1;
      }
      
      console.log('click', options, next[nextIdx]);
      
      updateView();
    }
    
    var btn1 = document.getElementById('one');
    var btn2 = document.getElementById('two');
    
    function updateView() {
      next = getNextQuestion();
      if (next) {
        btn1.innerHTML = next[0];
        btn2.innerHTML = next[1];
      } else {
        btn1.innerHTML = 'FINISH';
        btn2.innerHTML = 'FINISH';
      }
      
      printResults();
    }
    
    updateView();

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<button id="one" onclick="choose(0)"></button> vs. <button id="two" onclick="choose(1)"></button>
<div id="results"></div>

- webdeb

0

尝试创建一个项目数组，其中包含选择名称，使用元素，选择后删除元素，并将值推送到对象的三个属性之一。对象的属性1将包含一个项目，属性2将包含输入数组长度/ 3个项目，属性3将包含其余的选择；当form中只剩下一个选择选项时，将提供“none”。

var arr = [
  "apple",
  "orange",
  "banana",
  "cherry",
  "cabbage" 
];

var data = {
  "1": [],
  "2": [],
  "3": []
};

var form = document.forms["choices"];

var html = arr.map(function(val, index) {
  var input = document.createElement("input");
  var label = document.createElement("label");
  label.textContent = val + ":";
  input.type = "radio";
  input.name = "choice";
  input.className = "choices";
  input.value = val;
  label.appendChild(input);
  return label.outerHTML
});

form.lastElementChild
.insertAdjacentHTML("beforebegin", html.join("") + "<br>");

form.onchange = function(e) {
  e.preventDefault();
  if (data[1].length + data[2].length + data[3].length < arr.length - 2) {
    if (data[1].length === 0) {
      data[1].push(e.target.value);
    } else {
      if (data[2].length < arr.length / 3) {
        data[2].push(e.target.value);
      } else {
        data[3].push(e.target.value);
      }
    }
    form.removeChild(e.target.parentElement);
  } else {
    if (data[1].length + data[2].length + data[3].length === arr.length - 2) {
      data[3].push(e.target.value);
      form.removeChild(e.target.parentElement);
      var input = document.createElement("input");
      var label = document.createElement("label");
      label.textContent = "none";
      input.type = "radio";
      input.name = "choice";
      input.className = "choices";
      input.value = "none";
      label.appendChild(input);
      form.getElementsByClassName("choices")[0].parentElement
        .insertAdjacentHTML("afterend", label.outerHTML)
    } else {
      data[3].push(e.target.value);
      form.removeChild(e.target.parentElement);
      form.removeChild(form.getElementsByClassName("choices")[0].parentElement);
      form.firstElementChild.innerHTML = "Results:";
      form.querySelector("pre").textContent = JSON.stringify(data, null, 2)
    }
  }

  console.log(e.target.value, data);
}

<form name="choices">
  <span>Select one:</span>
  <br>
  <pre name="result"></pre>
</form>

- guest271314

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- m69 ''snarky and unwelcoming'' · Accepted Answer

我曾经在回答一个相关问题时（基于1对1选择的协作排序算法），研究过这个问题，并发现使用尽可能少的问题，同时避免循环（如：A>B，B>C，C>A）来创建基于“你更喜欢A还是B？”风格问题的有序列表，最好使用二进制插入排序或其变体。

实际上，这意味着您逐个将元素引入有序列表中，找到它们的位置，插入它们，然后继续下一个元素。
为了将比较次数减少到最小，您可以使用二进制插入；这意味着每个新元素首先与有序列表的中间元素进行比较；这告诉您新元素是放在上半部分还是下半部分；然后将其与该半部分的中间元素进行比较，以此类推，直到找到其位置。

例如，考虑需要排序的10个元素的列表。如果您将每个元素与其他每个元素进行比较，则必须问45个问题。通过二进制插入，这可以减少到19~25个问题，平均为22.2个问题。

问题的确切数量取决于输入：要将1插入到列表[2,4,6,8]中，您需要将其与4进行比较，然后与2进行比较，然后通过两次比较了解其位置；要将7插入到列表[2,4,6,8]中，您需要将其与4进行比较，然后与6进行比较，然后与8进行比较，并且只有在三次比较之后才知道其位置。通常，插入第n个元素需要log₂(n)或log₂(n)+1次比较（如果n是2的幂，则始终为log₂(n)）。总比较次数< n.log_e(n)。

如果接受“没有偏好”的答案，则问题的数量可以更少，如果大多数答案是“没有偏好”，则可以降至n-1。

下面是我为相关问题编写的JavaScript代码片段。它提出“A还是B？”问题，将“A”、“B”或“没有偏好”作为答案，并创建一个有序列表。随机生成器充当给出答案的人。

该算法可以适应原地排序的需求。首先将第一个元素视为已排序数组，将第二个元素视为要插入的元素，如果必要则交换它们；然后将前两个元素视为已排序列表，将第三个元素视为要插入的元素，以此类推。如需了解二分插入排序的变体和减少交换次数的策略，请参见维基百科文章。

function PrefList(n) {
    this.size = n;
    this.items = [{item: 0, equals: []}];
    this.current = {item: 1, try: 0, min: 0, max: 1};

    this.addAnswer = function(x, y, pref) {
        if (pref == 0) {
            this.items[this.current.try].equals.push(this.current.item);
            this.current = {item: ++this.current.item, try: 0, min: 0, max: this.items.length};
        } else {
            if (pref == -1) this.current.max = this.current.try
            else this.current.min = this.current.try + 1;
            if (this.current.min == this.current.max) {
                this.items.splice(this.current.min, 0, {item: this.current.item, equals: []});
                this.current = {item: ++this.current.item, try: 0, min: 0, max: this.items.length};
            }
        }
    }

    this.getQuestion = function() {
        if (this.current.item >= this.size) return null;
        this.current.try = Math.floor((this.current.min + this.current.max) / 2);
        return({a: this.current.item, b: this.items[this.current.try].item});
    }

    this.getOrder = function() {
        var index = [];
        for (var i in this.items) {
            var equal = [this.items[i].item];
            for (var j in this.items[i].equals) {
                equal.push(this.items[i].equals[j]);
            }
            index.push(equal);
        }
        return(index);
    }
}

// THIS FUNCTION ACTS AS THE PERSON ANSWERING THE QUESTIONS
function preference(a, b) {
    if (Math.random() > 0.6) return -1; else if (Math.random() > 0.333) return  1; else return 0;
}

// CREATE TABLE AND ASK QUESTIONS UNTIL TABLE IS COMPLETE
var fruit = ["orange", "apple", "pear", "banana", "kiwifruit", "grapefruit", "peach", "cherry", "starfruit", "strawberry"];
var t = new PrefList(10), c = 0, q;
while (q = t.getQuestion()) {
    document.write(++c + ". " + fruit[q.a] + " or " + fruit[q.b] + "?<BR>");
    var answer = preference(fruit[q.a], fruit[q.b]);
    document.write("&nbsp;&rarr; " + [fruit[q.a], "no preference", fruit[q.b]][answer + 1] + "<BR>");
    t.addAnswer(q.a, q.b, answer);
}

// PERFORM SORT BASED ON TABLE AND DISPLAY RESULT
var index = t.getOrder();
document.write("LIST IN ORDER:<BR>");
for (var i = 0, pos = 1; i < index.length; i++) {
    var pre = pos + ". ";
    for (var j = 0; j < index[i].length; j++) {
        document.write(pre + fruit[index[i][j]] + "<BR>");
        pre = "&nbsp;&nbsp;&nbsp;&nbsp;";
    }
    pos += index[i].length;
}