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
| R   2017-03-16 23:03 3 Answers

Answers ( 3 )

  1. 2017-03-17 00:03

    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. 2017-03-17 00:03

    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.

  3. 2017-03-17 01:03

    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
    
◀ Go back