## 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 ( 3 )

One possibility off the top of my head: a slightly modified bubble sort where you swap if

`x[j] + 1 == x[j + 1]`

:This has time-complexity

`O(N^2)`

, but what you are doing now is essentially a bogosort, which is`O(N!)`

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

`sort()`

.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: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:

Assuming the hash function has constant-time insertion, this will run in

`O(n)`

time.Here's a more R style way: