CODEWITHSUNDEEP
r
d.b
d.b

Reputation: 32548

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

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

Upvotes: 3

Views: 122

Answers (3)

thc
thc

Reputation: 9705

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

Upvotes: 3

bright-star
bright-star

Reputation: 6447

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
26ab0db90d72e28ad0ba1e22ee510510

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.

Upvotes: 1

Marius
Marius

Reputation: 60080

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!)

Upvotes: 3

Related Questions