如何重新排列矢量，使連續的整數不會彼此相鄰？

說我有一個整數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

如何重新排列矢量，使連續的整數不會彼此相鄰？

回答

相關問題