Wie man einen Vektor neu anordnet, damit aufeinander folgende ganze Zahlen nicht nebeneinander sind?

Question

Sagen, ich habe einen Vektor von ganzen Zahlen x

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

I x, so dass, wenn irgendwelche aufeinanderfolgenden ganzen Zahlen vorhanden neu anordnen müssen, sind in x, sie einen anderen (wenn überhaupt) nicht neben sind zu eins. Im Moment habe ich eine Schleife. Gibt es einen besseren Weg?

Werte in x müssen nicht unbedingt eindeutig sein. Aber jetzt können Sie davon ausgehen, dass die Anordnung x in der Art, wie ich will, immer möglich ist () Ich muss tatsächlich einen Weg finden zu bestimmen, ob x kann so angeordnet werden, wie ich oben erwähnt, aber das kann eine zweite Frage sein).

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 

Answer 1

Hier ist ein weiterer R-Stil Weg:

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 

Answer 2

Eine Möglichkeit aus der Spitze von meinem Kopf: eine leicht modifizierte Blase Art, wo Sie, wenn x[j] + 1 == x[j + 1] tauschen:

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

Das hat Zeit-Komplexität O(N^2), aber was machst du jetzt im Wesentlichen ein Bogosort, die O(N!)

Answer 3

Hier ist eine Skizze einer Lösung aus meinem früheren Kommentar:

1. Hash jedes Element des Vektors mit dem einfachsten Hash, der ausreichend diffusion für Ihr Eingabefeld hat, und speichern Sie diese in einem anderen Ausgabevektor. Es sieht so aus, als hätte R die digest-Bibliothek für diesen Job.
2. Sortieren Sie den Ausgabevektor in aufsteigender/absteigender Reihenfolge und speichern Sie den Vektor der neu geordneten Indizes, wobei R sort() ergibt.
3. Indexieren Sie den ursprünglichen Vektor mit den neu angeordneten Indizes.

meisten Hash-Funktionen sind so konzipiert, drastisch mit einer einzigen Änderung in der Ausgabe zu ändern, mit hohen Wahrscheinlichkeit zu md5(2), md5(1) sollte so nicht aufeinander folgend sein:

$ echo 1 | md5 
b026324c6904b2a9cb4b88d6d61c81d1 

$ echo 2 | md5 
26ab0db90d72e28ad0ba1e22ee510510 

Wie in den Kommentaren erwähnt, hängt auf den Elementen des Vektors ist einzigartig. Wenn dies nicht der Fall ist, fügen Sie dem Element eine Zufallszahl hinzu, unmittelbar bevor Sie es hashen. Vielleicht möchten Sie auch besonders Ihre Eingaben Fuzz, wenn Sie einen kleinen Satz haben, als Marius in den Kommentaren erwähnt:

> 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 

Unter der Annahme, die Hash-Funktion hat eine konstante Zeit Insertion, dies in O(n) Zeit ausgeführt wird.