distancePermutationLevenshtein {CEGO}

Levenshtein Distance for Permutations

Description

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.

Usage

distancePermutationLevenshtein(x, y)

Arguments

x

first permutation (integer vector)

y

second permutation (integer vector)

Value

numeric distance value

d(x,y)

, scaled to values between 0 and 1 (based on the maximum possible distance between two permutations)

References

Levenshtein, Vladimir I. "Binary codes capable of correcting deletions, insertions and reversals." Soviet physics doklady. Vol. 10. 1966.

Examples

x <- 1:5
y <- c(1,2,5,4,3)
distancePermutationLevenshtein(x,y)
p <- replicate(10,sample(1:5),simplify=FALSE)
distanceMatrix(p,distancePermutationLevenshtein)