通过用户的preference排序一组对象 [英] Sorting a set of objects by a user's preference
问题描述
由于（在这个例子中 N = 5 ）的一组n个对象在没有特定的顺序：
{
苹果，
橙，
香蕉，
樱桃，
卷心菜
}
我想给用户几个问题有三个选项，如下所示：
香蕉与白菜
（无preference）
每一个问题后，它会使不同的选项（没有preference保持不变），有效地收集用户的preferences数据。
一个新问题有将后（在此情况下6或7）的几个问题，给予以排名最高的对象的有序列表（阵列）：
{
樱桃，
卷心菜，
橙，
苹果，
香蕉
}
不过，我不知道这样的算法是如何工作的，或何时会知道停下来。我很抱歉，如果这是一个坏的问题，但我是pretty的新算法设计。
和我想这并不重要，但我使用JavaScript。
好吧，我重新审视这四个月后，因为我想到了一个新的方法来进行排序。
也许，这将是更有效的有下级为每个对象的一个列表，以便任何它不如一个目的将是低劣其上级。我解释这个要命，所以这里是一个可视化的：
樱桃＆GT;卷心菜
白菜＆GT;香蕉
白菜＆GT;苹果
苹果＆GT;橙
因此，樱桃＆GT;白菜和放大器;香蕉和放大器;苹果和放大器;橙
使用老方法，用得分：
苹果与橘子
苹果与香蕉（例如苹果胜）
苹果与樱桃（例如樱桃胜）
苹果与白菜
橙色与香蕉
橙色与樱桃
橙色与白菜
香蕉与樱桃
香蕉对白菜
樱桃与白菜
10个问题
新的方法将使樱花主场迎战香蕉多余的，因为我们已经知道，苹果＆GT;香蕉和樱桃＆GT;苹果。我真的只需要找出如何code吧。
唯一的问题就出现了与人类的循环逻辑（即 A＆GT; B＆GT; C＆gt;一种），其中，这是一种可能性，但幸运的是这不会与我的特别设置的一个问题。
我前一段时间看着这是我的回答对一个相关的问题的一部分（<一href="http://stackoverflow.com/questions/31976519/collaborative-sorting-algorithm-based-on-1-vs-1-choice/32002512#32002512">Collaborative排序根据1对1的选择算法），发现创建一个有序列表的基础上做你preFER 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] ，你会用<$比较C $ C> 4 6 ，然后用 8 ，只知道后三个比较它的位置。在一般情况下，插入第n个元素既需要登录 2 （n）或登录 2 （N）+1的比较（总是登录 2 （n）的，如果n是2的幂）。总的复杂性和LT; n.log <子>电子（N）。
如果您接受无preference的答案，问题的数量可以低一些，下降到n-1，如果大部分的答案是没有preference。
下面是一个Javascript code片断，我写了相关的问题。它要求A或B？的问题，以A，B或无preference作为答案，并创建一个有序列表。一个随机数发生器作为提供答案的人。
该算法可适于就地阵列排序。你会通过考虑第一元素作为排序后的数组启动，并且要被插入的第二元件为元件，并在必要时交换它们;那么您会考虑前两个元素作为排序列表，并且要被插入的第三个元素作为元素，依此类推。对于二进制插入排序的变化，以及战略，以减少交换的数量，例如见这个维基百科文章。
函数prefList（N）{
this.size = N;
this.items = [{项目：0，等于：[]}];
this.current = {项目：1，尽量：0分：0，最大值：1};
this.addAnswer =功能（X，Y，preF）{
如果（preF == 0）{
this.items [this.current.try] .equals.push（this.current.item）;
this.current = {项目：++ this.current.item，试试：0分：0，最大值：this.items.length};
} 其他 {
如果（preF == -1）this.current.max = this.current.try
别的this.current.min = this.current.try + 1;
如果（this.current.min == this.current.max）{
this.items.splice（this.current.min，0，{项目：this.current.item，等于：[]}）;
this.current = {项目：++ this.current.item，试试：0分：0，最大值：this.items.length};
}
}
}
this.getQuestion =功能（）{
如果（this.current.item＆GT; = this.size）返回NULL;
this.current.try = Math.floor（（this.current.min + this.current.max）/ 2）;
回报（{A：this.current.item，B：this.items [this.current.try] .item}）;
}
this.getOrder =功能（）{
VAR指数= [];
为（在this.items变种I）{
VAR等于= [this.items [I] .item]。
为{（在this.items [I] .equals变种j）条
equal.push（this.items [I] .equals [J]）;
}
index.push（等于）;
}
回报（指数）;
}
}
//这个函数作为回答问题的PERSON
函数preference（A，B）{
如果（的Math.random（）＆GT; 0.6）返回-1;否则，如果（的Math.random（）＆GT; 0.333），回归1;否则返回0;
}
// create table和问问题，直到表完成
无功果= [橙色，苹果，梨花，香蕉，奇异果，柚子，桃花，樱桃，杨桃，草莓];
变种T =新的prefList（10），C = 0，Q;
而（Q = t.getQuestion（））{
的document.write（。+ + C + +水果[QA] +或+水果[QB] +＆LT; BR＆gt;中）;
VAR答案= preference（水果[q.a]，水果[q.b]）;
的document.write（＆安培; NBSP;＆安培; RARR;+果[QA]，无preference，水果[QB] [答案+ 1] +＆其中; BR＆gt;中）;
t.addAnswer（q.a，q.b，答案）;
}
//执行排序基于表并显示结果，
VAR指数= t.getOrder（）;
文件撰写（LIST依次是：＆LT; BR＆gt;中）;
对于（VAR I = 0，POS = 1; I＆LT; index.length;我++）{
VAR pre = POS +。;
对于（VAR J = 0; J＆LT;指数[I] .length; J ++）{
文件撰写（pre +果[指数[I] [J] +＆LT; BR＆gt;中）;
pre =＆放大器; NBSP;＆安培; NBSP;＆安培; NBSP;＆安培; NBSP;;
}
POS + =指数[I] .length;
}
Given a set of n objects in no specific order (n = 5 in this example):
{
apple,
orange,
banana,
cherry,
cabbage
}
I'm trying to give a user several questions with three options, like so:
banana vs. cabbage
(no preference)
after every question, it would make a new question with different options (no preference stays the same), efficiently collecting data on the user's preferences.
It would, after several (6 or 7 in this case) questions, give an ordered list (array) of the highest ranked objects in order:
{
cherry,
cabbage,
orange,
apple,
banana
}
However, I don't know how such an algorithm would work or when it would know to stop. I'm sorry if this is a bad question, but I'm pretty new to algorithm design.
And I suppose it doesn't really matter, but I'm using JavaScript.
Okay, I'm revisiting this four months later, because I thought of a new method to do the sorting.
Perhaps, it would be more efficient to have a list of inferiors for each object, so that anything which is inferior to one object would be inferior for its superiors. I'm explaining this awfully, so here's a visual:
cherry > cabbage
cabbage > banana
cabbage > apple
apple > orange
thus, cherry > cabbage & banana & apple & orange
With the old method, with score:
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
The new method would make cherry vs. banana redundant because we already know that apple > banana and cherry > apple. I really only need to figure out how to code it.
The only problem arises with human circular logic (i.e. a > b > c > a), where this is a possibility, but thankfully this won't be a problem with my particular set.
I looked into this some time ago as part of my answer to a related question (Collaborative sorting algorithm based on 1 vs 1 choice) and found that creating an ordered list based on "do you prefer A or B?" style questions, using as few questions as possible, and while avoiding cycles (as in: A>B, B>C, C>A), is best done using binary insertion sort, or a variation thereof.
What this means in practise, is that you introduce the elements into the ordered list one by one, find their place in the list, insert them, and then move on to the next element.
To reduce the number of comparisons to the strictest minimum, you use binary insertion; this means that every new element is first compared to the element in the middle of the ordered list; this tells you whether the new element goes in the upper or lower half; then you compare it to the element in the middle of that half, and so on, until its place is found.
As an example, consider a list of 10 elements that need to be sorted. If you compared every element with every other element, you'd have to ask 45 questions. With binary insertion, this is reduced to 19 ~ 25 questions, with an average of 22.2 questions.
The exact number of questions depends on the input: to insert 1 into the list [2,4,6,8], you'd compare it with 4, then with 2, and you'd know its location with two comparisons; to insert 7 into the list [2,4,6,8], you'd compare it with 4, then with 6, then with 8, and only know its location after three comparisons. In general, inserting the n-th elements takes either log2(n) or log2(n)+1 comparisons (always log2(n) if n is a power of 2). The overall complexity < n.loge(n).
If you accept "no preference" answers, the number of questions can be lower, down to n-1 if most of the answers are "no preference".
Below is a Javascript code snippet I wrote for the related question. It asks "A or B?" questions, takes "A", "B" or "no preference" as answers, and creates an ordered list. A random generator acts as the person giving the answers.
The algorithm could be adapted to sort the array in-place. You'd start by considering the first element as the sorted array, and the second element as the element to be inserted, and swap them if necessary; then you'd consider the first two elements as the sorted list, and the third element as the element to be inserted, and so on. For variations of binary insertion sort, and strategies to reduce the number of swaps, see e.g. 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(" → " + [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 = " ";
}
pos += index[i].length;
}
这篇关于通过用户的preference排序一组对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
