Insert Distance for Permutations
The Insert Distance is an edit distance. It counts the minimum number of delete/insert operations required to transform one permutation into another. A delete/insert operation shifts one element to a new position. All other elements move accordingly to make place for the element. E.g., the following shows a single delete/insert move that sorts the corresponding permutation: 1 4 2 3 5 -> 1 2 3 4 5.
distancePermutationInsert(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)
Schiavinotto, Tommaso, and Thomas Stuetzle. "A review of metrics on permutations for search landscape analysis." Computers & operations research 34.10 (2007): 3143-3153.
Wikipedia contributors, "Longest increasing subsequence", Wikipedia, The Free Encyclopedia, 12 November 2014, 19:38 UTC, <http://en.wikipedia.org/w/index.php?title=Longest_increasing_subsequence&oldid=633565014> [accessed 13 November 2014]
x <- 1:5 y <- c(5,1,2,3,4) distancePermutationInsert(x,y) p <- replicate(10,sample(1:5),simplify=FALSE) distanceMatrix(p,distancePermutationInsert)
Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.