distancePermutationSwap {CEGO}

Swap-Distance for Permutations

Description

The swap distance is an edit-distance, counting how many edit operation (here: swaps, i.e., transposition of two adjacent elements) have to be performed to transform permutation x into permutation y. Note: In v2.4.0 of CEGO and earlier, this function actually computed the swap distance on the inverted permutations (i.e., on the rankings, rather than orderin). This is now (v2.4.2 and later) corrected by inverting the permutations x and y before computing the distance (ie. computing ordering first). The original behavior can be reproduced by distancePermutationSwapInv. This issue was kindly reported by Manuel Lopez-Ibanez and the difference in terms of behavior is discussed by Ekhine Irurozki and him (2021).

Usage

distancePermutationSwap(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

Schiavinotto, Tommaso, and Thomas Stuetzle. "A review of metrics on permutations for search landscape analysis." Computers & operations research 34.10 (2007): 3143-3153.

Irurozki, Ekhine and Ibanez-Lopez Unbalanced Mallows Models for Optimizing Expensive Black-Box Permutation Problems. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2021. ACM Press, New York, NY, 2021. doi: 10.1145/3449639.3459366

Examples

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