A measure of similarity between two lists

Question

I am trying to calculate an algorithm that gives a measure of similarity between two lists, each of which has n distinct elements. These two lists are basically different locations of the same elements.

Answer 1

One way is to calculate the editing distance, that is, the minimum number of modification steps, to convert one list to another. This will be basically the same as the Levenshtein or Damerau-Levenshtein distance, but instead of a character string, you are comparing a list of elements.

http://en.wikipedia.org/wiki/Levenshtein_distance

Answer 2

It looks like you are looking for metric over permutations . This document is an overview of several possibilities.