将每个值交换为不同的值

Question

下面是交换函数，它交换列表中小于10的值

swapFun <- function(x, n = 10){
inx <- which(x < n)
x[sample(inx)] <- x[inx]
x
}

例如，原始列表是1，2，3，10，4，11。

通过采样进行交换后，此列表可以是2、1、4、10、3、11或1、3、2、10、4、11。

但是我想把每个小于10的值换成另一个小于10的值。

例如，第一个结果(即2，1，4，10，3，11)是我想要的，因为每个小于10的值都被交换为小于10的不同值。

然而，第二个结果(即1，3，2，10，4，11。)不是我想要的，因为1和4还没有交换到小于10的不同值。

如果没有可行方案，只需打印“没有可行方案”即可。

有什么建议吗？非常感谢。

Answer 1

您正在寻找一个值小于10的derangement。根据错位排列理论，大约1/e (37%)的随机选择的排列是错位排列，因此命中或未命中的方法是合理的，但有一个重要的警告。

在小于n的项目之间可能存在重复。并不是所有这些项的排列都是可区分的，所以并不是所有项的错乱看起来都像错乱：(例如)相互交换两个2在某种意义上是错乱的，但它看起来不像错乱。1/e启发式适用于位置的原始排列，而不是值的可区分排列。如果重复次数很高，可能需要比建议的1/e更长的时间。如果在您的用例中性能不能令人满意，则需要将函数定义中的sample()替换为一个更复杂的函数，该函数可选择随机可区分的排列。

就可行性而言，只要小于n的最常见元素不占小于n的项目的50%以上，就会有可行的解决方案

derangement <- function(x){
  if(max(table(x)) > length(x)/2) return(NA)
  while(TRUE){
    y <- sample(x)
    if(all(y != x)) return(y)
  }
}

swapFun <- function(x, n = 10){
  inx <- which(x < n)
  y <- derangement(x[inx])
  if(length(y) == 1) return(NA) 
  x[inx] <- y
  x
}

例如,

> set.seed(10)
> swapFun(c(1,2,10,4,11,2,12))
[1]  2  4 10  2 11  1 12
> swapFun(c(2,2,10,4,11,2,12))
[1] NA

请注意，没有有效的乱序长度为1，但NA的长度为1，因此测试y的长度是测试是否可能对这些值进行乱序的有效方法。如果不存在小于n的值的乱序，则该函数返回NA。如果需要，您可以测试NA并打印“没有可行的解决方案

Answer 2

此函数为您提供数字= m的位置不变。

require(combinat)

x <- c(1,2,10,4,11,2,12)
m <- 10

swapFun <- function(x, m){

  # determine positions of values to be permutated or fixed
  xi <- which(x < m)
  xj <- which(x >= m)

  # make permuations
  xp <- do.call(rbind, permn(x[xi]))

  # make matrix with permutated and fixed values
  xn <- matrix(nrow = nrow(xp), ncol = length(x))
  xn[ ,xi] <- xp
  xn[ ,xj] <- sort(rep(x[xj],nrow(xp)))

  # delete duplicates
  d <- !duplicated(apply(xn, 1, paste, collapse = "_"))
  xn <- xn[d,]

  return(xn)
}

swapFun(x,m)

> swapFun(x,m)
        [,1] [,2] [,3] [,4] [,5] [,6] [,7]
 [1,]    1    2   10    4   11    2   12
 [2,]    1    2   10    2   11    4   12
 [3,]    2    1   10    2   11    4   12
 [4,]    2    1   10    4   11    2   12
 [5,]    1    4   10    2   11    2   12
 [6,]    4    1   10    2   11    2   12
 [7,]    4    2   10    1   11    2   12
 [8,]    2    4   10    1   11    2   12
 [9,]    2    4   10    2   11    1   12
[10,]    4    2   10    2   11    1   12
[11,]    2    2   10    4   11    1   12
[12,]    2    2   10    1   11    4   12