What are some good ways to calculate a score for how difference or close 2 users choices are?

For example, if it is the choice of chocolate, ice cream, donut, ..., for the order of their preference.

If user 1 choose

A B C D E F G H I J

and user 2 chooses

J A B C I G F E D H

what are some good ways to calculate a score from 0 to 100 to tell how close their choices are? It has to make sense, such as if most answers are the same but just 1 or 2 answers different, the score cannot be made to extremely low. Or, if most answers are just "shifted by 1 position", then we cannot count them as "all开发者_StackOverflow中文版 different" and give 0 score for those differences of only 1 position.

---

Assign each letter item an integer value starting at 1 A=1, B=2, C=3, D=4, E=5, F=6 (stopping at F for simplicity) Then consider the order the items are placed, use this as a multiple So if a number is the first item, its multiplier is 1, if its the 6th item the multipler is 6 Figure out the maximum score you could have (basically when everything is in consecutive order)

item  a  b  c  d  e  f 
order 1 2 3 4 5 6 
value 1 2 3 4 5 6 
score 1 4 9 16 25 36 Sum = 91, Score = 100% (MAX)

item a b d c e f    
order 1 2 3 4 5 6        
value 1 2 4 3 5 6    
score 1 4 12 12 25 36 Sum =  90 Score = 99%

=======================

order 1 2 3 4 5 6    
item  f  d  b  c  e  a    
value 6 4 2 3 5 1    
score 6 8 6 12 25 6 Sum =  63 Score =  69%



order 1 2 3 4 5 6    
item  d  f  b  c  e  a    
value 4 6 2 3 5 1    
score 4 12 6 12 25 6 Sum =  65 Score =  71%

obviously this is a very crude implementation that I just came up with. It may not work for everything. Examples 3 and 4 are swapped by one position yet the score is off by 2% (versus ex 1 and 2 which are off by 1%). It's just a thought. I'm no algorithm expert. You could probably use the final number and do something else to it for a better numerical comparison.

---

You could

1. Calculate the edit distance between the sequences;
2. Subtract the edit distance from the sequence length;
3. Divide that by the length of the sequence
4. Multiply it by hundred

---

Score = 100 * (SequenceLength - Levenshtein( Sequence1, Sequence2 ) ) / SequenceLength

Edit distance is basically the number of operations required to transform sequence one in sequence two. An algorithm therefore is the Levenshtein distance algorithm.

---

Examples:

Weights
  insert: 1
  delete: 1
  substitute: 1

Seq 1: ABCDEFGHIJ
Seq 2: JABCIGFEDH

Score = 100 * (10-7) / 10 = 30

Seq 1: ABCDEFGHIJ
Seq 2: ABDCFGHIEJ

Score = 100 * (10-3) / 10 = 70

---

The most straightforward way to calculate it is the Levenshtein distance, which is the number of changes that must be done to transform one string to another.

Disadvantage of Levenshtein distance for your task is that it doesn't measure closeness between products themselves. I.e. you will not know how A and J are close to each other. For example, user 1 may like donuts, and user 2 may like buns, and you know that most people who like first also like the second. From this information you can infer that user 1 makes choices that are close to choices of user 2, through they don't have same elements.
If this is your case, you will have to use one of two: statistical methods to infer correlation between choices or recommendation engines.