将每个值交换为不同的值

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,1,10,1,11或1,3,2,10,4,11.

但我想将每个小于10的值交换为小于10的不同值.

例如,第一个结果(即2,1,1,10,1,11)就是我想要的,因为每个小于10的值都被交换到小于10的不同值.

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

如果没有可行的解决方案,只需打印"没有可行的解决方案"

有什么建议？非常感谢.

Answer 1

你正在寻找小于10的值的紊乱.根据紊乱理论,大约1/e(37%)的随机选择的排列是紊乱,所以命中或错过的方法是合理的,有一个重要的警告.

不到的项目可能会重复n.并非所有这些项目的排列都是可区分的,因此并非所有项目的紊乱看起来都像紊乱:彼此交换两个2(例如)在某种意义上是一种紊乱,但它看起来不像是一种紊乱.该1/e启发式适用于位置的原始排列,价值没有区别排列.如果重复次数很高,则可能需要超过1/e的时间.如果在您的用例中性能不令人满意,则需要sample()在函数定义中替换一个更复杂的函数,该函数选择随机可区分的排列.

就可行性而言,只要最常见的元素少于n不超过50%的项目,就会有一个可行的解决方案.n

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是测试是否可以解除值的有效方法.NA如果不存在小于n的值的紊乱,则函数返回.如果需要,您可以测试NA并打印"无可行解决方案"