javascript - 根据用户的偏好对一组对象进行排序

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

我前段时间在回答相关问题 (Collaborative sorting algorithm based on 1 vs 1 choice) 时对此进行了调查，发现创建一个基于“你喜欢 A 还是 B？”的有序列表样式问题，使用尽可能少的问题，同时避免循环(如:A>B，B>C，C>A)，最好使用二进制插入排序或其变体来完成。

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

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

问题的确切数量取决于输入:要将 1 插入列表 [2,4,6,8]，您需要将它与 4 进行比较，然后是2，比较两次就知道它的位置了；要将 7 插入列表 [2,4,6,8]，您需要将它与 4 进行比较，然后再与 进行比较6，然后跟8，比较3次才知道它的位置。通常，插入第 n 个元素需要进行 log₂(n) 或 log₂(n)+1 次比较(总是 log₂ (n) 如果 n 是 2 的幂)。总的比较次数< n.log_e(n)。

如果您接受“无偏好”的答案，问题的数量可以减少，如果大多数答案都是“无偏好”，则问题数量可以减少到 n-1。

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

该算法可以适用于就地对数组进行排序。您首先将第一个元素视为排序数组，将第二个元素视为要插入的元素，并在必要时交换它们；那么您会将前两个元素视为排序列表，将第三个元素视为要插入的元素，依此类推。有关二进制插入排序的变体以及减少交换次数的策略，请参见例如this Wikipedia article .

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;
}