Sorting a set of objects by a user's preference

Question

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.

Answer 1

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 log₂(n) or log₂(n)+1 comparisons (always log₂(n) if n is a power of 2). The overall number of comparisons < n.log_e(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("&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;
}

Answer 2

You can use 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 3

I wrote a small jsFiddle for your problem using angular-js (You don't need to use angular)

The idea is to compare every element to every other element. Once every element has been compared to every other element, you'r done. In the code, focus on the getNext() function:

$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();   
    }
}

The first two if statements are used to determine the winner.

As you can see, I'm using variables x and y to store the current position in your matrix. First I compare food number 0 (= x) with 1, 2, 3, 4 ( =y). When y reaches array.length-1, you add 1 to x and set y to x +1. When x reaches array.length-2 and y array.length-1 it means, that you compared everything to everything else. Now you can sort the array by the score and you are done :)

Edit: Here is the new Fiddle which adds the possibility to answer with "indifferent".

One more thing you need to consider: When dealing with preferences in theory, there are three axioms Some explanation:

1. Completeness: Every Object can be compared to every other object
2. Reflexivity: Every Object is at least as good as itself
3. Transitivity: If a > b and b > c, this has to mean that a > c.

These axioms have to apply, so that you can calculate with utility functions.

But in practice especially the third one doesn't apply. You will always find people who say: Oranges > apples, apples > bananas BUT ALSO bananas > oranges

In my fiddle I ignored those axioms and let the user decide wether they want to act completely logical or not.

Answer 4

You don't need to compare every item against every other item. That would require you to ask the user 15 questions to sort 5 items. It's been proven that you can get a total ordering of 5 items in 7 comparisons.

You can accomplish this with a sorting network. For any N, you can create a series of comparisons and swaps that will sort the items. There are known optimum sequences for sorting up to 16 items. Beyond that there are algorithms that will generate sorting networks (see Constructing sorting networks in the linked article). Although those networks are not proven to be optimum, they're probably more efficient than a general-purpose sorting algorithm.

Your larger problem, which I think you gloss over too easily, is the very real possibility of circular logic. Transitivity typically doesn't hold when it comes to user preferences.

Answer 5

Well you could add weight to each item based on the users answers. So for instance in your example of

banana      vs.      cabbage
      (no preference)

When the user selects banana you add a plus one to the banana item. If they select cabbage you give plus one to cabbage and then if they select no preference then you can just give neither a plus one. Then you can sort the list from the largest value to the smallest.

Answer 6

Use a map (javascript object can act so) with object as the key and integer (set to 0 initially for all objects) as the value.

For each question, you increment the value of the respective chosen key. Since no preference affects none of them, nothing to be done in case it's chosen.

Then iterate the map, finding the key-value pair with highest value. Return the key.

Answer 7

1. Keep all of the items in an array. Use a separate array / hashmap for relations between pairs. Then use your favorite comparison-based search algorithm (say quicksort).

2. When two elements are to be compared, find out relative precedence using the map. If there is no known precedence, ask the user.

3. When a new precedence is added, adjust the precedence order of the whole matrix. For example when the user says apple < banana and then separately banana < cherry, add apple < cherry to the hashmap.

The comparison-based search algorithms are designed to optimize number of comparisons and this translates to optimization of the number of questions asked to the user in this case.

Answer 8

Keep your elements in an array like this:

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

Now add the predecessors to the elements as the users choose their preferences. Let's say a user rated banana over orange, cabbage over orange, and cabbage over banana. Result:

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

Now sort the array using a custom comparator function:

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

Note that javascript has no native "contains" function for arrays. You can use $.inArray from jQuery or _.contains from underscore, or write one yourself.

Answer 9

Make it simple:

    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>

Answer 10

Try creating an array of items having selection names , using input type="radio" elements , removing elements as selected , pushing values to one of three properties of an object. Property 1 of object would contain one item , property 2 would contain input array length / 3 items , property 3 would contain remainder of selections; "none" would be provided when one selection option remains in form.

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>