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

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

我前段时间对此进行了研究,作为我对相关问题(基于1对1选择的协同排序算法)的回答的一部分,并发现根据"你更喜欢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,并且仅在三次比较后知道其位置.通常,插入第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;
}