如何重新排列矢量，使连续的整数不会彼此相邻？

说我有一个整数x如何重新排列矢量，使连续的整数不会彼此相邻？

x = c(1:3,6:7)

我需要重新排序的矢量x这样，如果任何连续的整数存在于x，他们不是彼此相邻（如果可能的话）。现在我有一个循环。有没有更好的办法？

x中的值不一定是唯一的。但现在你可以假设以我想要的方式排列x将永远是可能的（我实际上需要找出一种方法来确定x是否可以按照我上面提到的方式排列，但这可能是本身的第二个问题）。

set.seed(42) 
while(any(abs(diff(x)) == 1)){ 
    x = sample(x) 
    print(x) 
} 
#[1] 7 6 1 2 3 
#[1] 1 3 7 6 2 
#[1] 7 2 6 1 3

来源

2017-03-16 d.b

我们可以假设X值是唯一的？ – Gregor

这里有一个以上的R风格的方式：

myfunc <- function(y) { 
    yt <- table(y) 
    yt <- structure(.Data=as.vector(yt), .Names=names(yt)) 
    ys <- sort(as.numeric(names(yt))) 
    ys <- c(ys[seq(1,length(ys),2)],ys[seq(2,length(ys),2)]) 
    result <- lapply(ys, function(i) rep(i,yt[as.character(i)])) 
    result <- do.call(c, result) 
    return(result) 
} 

res <- myfunc(c(1,5,7,8,3,7,9,2,6,3,87,7,3,1,1,1,3)) 
print(res) 
[1] 1 1 1 1 3 3 3 3 6 8 87 2 5 7 7 7 9 

print(any(abs(diff(res)) == 1)) 
[1] FALSE

来源

2017-03-17 00:53:05 thc

另外，如果一个矢量不只有3个或2个连续的唯一整数，它总能以你想要的方式排序。所以7,8和3,4,4,5永远不能排序，但其他任何不符合该模式的排序都可以排序。 – thc

一个可能把我的头顶部：稍微修改冒泡排序，你交换，如果x[j] + 1 == x[j + 1]：

# Bubble sort implementation from: 
# https://www.r-bloggers.com/bubble-sorting-in-r-c-and-julia-code-improvements-and-the-r-compiler/ 
bubble_sort = function(vec) { 
    no_passes = 0 
    while(1) { 
     no_swaps = 0 
     for (j in 1 : (length(vec) - 1 - no_passes)) { 
      if (vec[j] + 1 == vec[j + 1]) { 
       s = vec[j] 
       vec[j] = vec[j+1] 
       vec[j+1] = s 
       no_swaps = no_swaps + 1 
      } 
     } 
     no_passes = no_passes + 1 
     if(no_swaps == 0) break 
    } 
    vec 
} 

x = c(1:3,6:7) 
bubble_sort(x)

这一次复杂O(N^2)，但你现在正在做的基本上是一个BOGO排序，这是O(N!)

来源

2017-03-16 23:06:16 Marius

看起来并不完美（'7'和'6'彼此相邻）。但我喜欢这个主意。 –

这是从我先前的评论的解决方案的草图：

用最简单的哈希散列向量的每个元素，该散列对于您的输入字段具有充足的diffusion，并将它们存储在另一个输出向量中。它看起来像R有这个工作digest图书馆。
按照递增/递减顺序对输出向量进行排序，并存储重新排序的索引向量，R会给你sort()。
使用重新排序的索引对原始向量进行索引。

大多数散列函数被设计为与输出一个变化发生急剧变化，所以md5(1)不应该是连续的，以md5(2)，以高概率：

$ echo 1 | md5 
b026324c6904b2a9cb4b88d6d61c81d1 

$ echo 2 | md5 
26ab0db90d72e28ad0ba1e22ee510510

正如评论所说，这取决于在向量的元素是独特的。如果它们不是，则在散列它之前向该元素添加一个随机数。您可能还需要进行模糊你的投入，特别是如果你有一个小集，马吕斯提到的评论：

> y = 1:5; y[order(sapply(y, function (n) { digest(n + runif(1), "md5")}))] 
[1] 5 1 3 2 4 
> y = 1:5; y[order(sapply(y, function (n) { digest(n + runif(1), "md5")}))] 
[1] 2 5 4 1 3

假设散列函数具有恒定的时间插入，这将在O(n)时间运行。

来源

2017-03-16 23:13:18

这并不能保证所需的顺序吗？如果你有'1,2,3'，那么不能保证说'hash（1） Marius

@Marius我误解了这个问题吗？我认为要求只是连续的元素不会彼此紧挨着。 –

我认为你的解决方案很有可能，但不能保证。当然，您可以在尝试后进行快速检查，如果失败，则为每个元素添加随机数字并再试一次。 – Marius

如何重新排列矢量，使连续的整数不会彼此相邻？

回答

相关问题