## How to reorder a vector so that consecutive integers are not next to one another?

Question

Say I have a vector of integers `x`

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

I need to reorder `x` such that if any consecutive integers are present in `x`, they are not next to one another (if possible at all). Right now I have a loop. Is there a better way?

Values in `x` will not necessarily be unique. But for now you can assume that arranging `x` in the way I want will always be possible (I actually need to find out a way to determine if `x` can be arranged the way I mentioned above, but that may be a second question by itself).

``````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
``````

Show source

## Answers to How to reorder a vector so that consecutive integers are not next to one another? ( 3 )

1. One possibility off the top of my head: a slightly modified bubble sort where you swap if `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)
``````

This has time-complexity `O(N^2)`, but what you are doing now is essentially a bogosort, which is `O(N!)`

2. Here is a sketch of a solution from my earlier comment:

1. Hash each of the elements of the vector with the simplest hash that has sufficient diffusion for your input field, and store those in another output vector. It looks like R has the digest library for this job.
2. Sort the output vector in increasing/decreasing order, and store the vector of reordered indices, which R will give you with `sort()`.
3. Index the original vector with the reordered indices.

Most hash functions are designed to change drastically with a single alteration in the output, so `md5(1)` should not be consecutive to `md5(2)`, with high probability:

``````\$ echo 1 | md5
b026324c6904b2a9cb4b88d6d61c81d1

\$ echo 2 | md5
``````

As mentioned in the comments, this depends on the elements of the vector being unique. If they are not, add a random number to the element just before you hash it. You may also want to fuzz your inputs especially if you have a small set, as Marius mentions in the comments:

``````> 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
``````

Assuming the hash function has constant-time insertion, this will run in `O(n)` time.

3. Here's a more R style way:

``````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
``````