Levenshtein Distance for Permutations
Levenshtein Distance, often just called "Edit Distance". The number of insertions, substitutions or deletions to turn one permutation (or string of equal length) into another.
distancePermutationLevenshtein(x, y)
x |
first permutation (integer vector) |
y |
second permutation (integer vector) |
numeric distance value
d(x,y)
, scaled to values between 0 and 1 (based on the maximum possible distance between two permutations)
Levenshtein, Vladimir I. "Binary codes capable of correcting deletions, insertions and reversals." Soviet physics doklady. Vol. 10. 1966.
x <- 1:5 y <- c(1,2,5,4,3) distancePermutationLevenshtein(x,y) p <- replicate(10,sample(1:5),simplify=FALSE) distanceMatrix(p,distancePermutationLevenshtein)
Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.