计算 R 中 `base::sort` 中的交换次数

Question

base::sort函数return无序向量的升（降）序。

X <- c(3,4,2,5,1)
sort(X)
[1] 1 2 3 4 5

有什么方法可以计算函数执行的交换次数以获得有序向量？

Answer 1

stringdist包可以对字符串进行这种计算。所以如果你有足够少的符号，你可以使用它。例如：

X <- c(3,4,2,5,1)
Y <- sort(X)

# Convert to strings
tostring <- function(x, symbols = sort(unique(x))) {
  alphabet <- c(letters, LETTERS)
  if (length(symbols) > length(alphabet))
    stop("You need a bigger alphabet!")
  if (any(! x %in% symbols))
    stop("x has unknown symbols!")
  paste(alphabet[match(x, symbols)], collapse="")
}

symboldist <- function(x, y, method = "osa") {
  symbols <- unique(c(x, y))
  stringdist::stringdist(tostring(x, symbols), tostring(y, symbols), 
                         method = method)
}

symboldist(X, Y)
#> [1] 4

^{由 reprex package (v2.0.0)}

于 2021-08-08 创建

编辑补充：看起来“换位距离”就是你想要的。这是一个基于 Javascript 的实现，在 https://www.geeksforgeeks.org/number-of-transpositions-in-a-permutation/:

# Translation of Javascript transposition distance calculation
# from https://www.geeksforgeeks.org/number-of-transpositions-in-a-permutation/

transpositionDistance <- function(P) {
  dfs <- function(i) {
    result <- 0
    while (!visited[i]) {
      visited[i] <<- TRUE
      i <- goesTo[i]
      result <- result + 1
    }
    result
  }
  
  # Convert P into a permutation of 1:n
  P <- match(P, sort(P))
  
  n <- length(P)
  if (!all(seq_len(n) %in% P))
    stop("this only works on permutations of unique elements")
  visited <- logical(n)
  goesTo <- integer(n)
  
  goesTo[P] <- seq_along(P)
  transpositions <- 0
  for (i in seq_len(n))
    if (!visited[i])
      transpositions <- transpositions + dfs(i) - 1
  transpositions
}

transpositionDistance(c(3,4,2,5,1))
#> [1] 4
transpositionDistance(c(1,3,5,2,4))
#> [1] 3
transpositionDistance(c(1,4,3,2,5))
#> [1] 1

计算 R 中 `base::sort` 中的交换次数

Counting the number of swaps in `base::sort` in R

sorting

swap

r