Finden und unterbrechen Sie wiederholte Läufe

Question

Ich habe einen Vektor mit sich wiederholenden Mustern. Ich möchte überall brechen, wo sich das sich wiederholende Muster der Länge n ändert. Hier die Daten:

x <- c(rep(1:4, 5), rep(5:6, 3), rep(c(1, 4, 7), 5), rep(c(1, 5, 7), 1), rep(2:4, 3)) 

## [1] 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 5 6 5 6 5 6 1 4 7 1 4 7 1 4 7 1 4 7 1 4 7 1 5 7 2 3 4 2 3 4 2 3 4 

Ich möchte das Muster diese Orte zu finden, um in der Lage verändert, so bricht es wie folgt aus:

Ich denke rle von Nutzen sein kann, aber nicht Siehe wie.

Answer 1

Hier ist eine Funktion, es zu tun. Das ist übrigens ein Problem in der Genetik - Tandem-Repeats zu finden. Here's a link to an algorithm paper das ist eine viel bessere Behandlung als das, aber viel komplizierter zu implementieren.

Die Ausgabe ist ein Vektor von Gruppen, in die x aufgeteilt werden soll.

Zunächst wird eine Hilfsfunktion:

factorise <- function(x) { 
    x <- length(x) 
    if(x == 1){return(1)} 
    todivide <- seq(from = 2, to = x) 
    out <- todivide[x %% todivide == 0L] 
    return(out) 
} 

Nun ist die Hauptfunktion:

findreps <- function(x, counter = NULL){ 
    if(is.null(counter)){ 
    counter <- c() 
    maxcounter <- 0 
    } else { 
    maxcounter <- max(counter) 
    } 
    holding <- lapply(1:length(x), function(y){x[1:y]}) 
    factors <- lapply(holding, factorise) 
    repeats <- sapply(1:length(factors), function(index) {any(sapply(1:length(factors[[index]]), function(zz) {all((rep(holding[[index]][1:(length(holding[[index]])/factors[[index]][zz])], factors[[index]][zz]))==holding[[index]])}))}) 
    holding <- holding[max(which(repeats))][[1]] 
    if(length(holding) == length(x)){ 
    return(c(counter, rep(maxcounter + 1, length(x)))) 
    } else { 
    counter <- c(counter, rep(maxcounter + 1, length(holding))) 
    return(findreps(x[(length(holding) + 1):length(x)], counter)) 
    } 
} 

Wie es funktioniert: Es ist eine rekursive Funktion, die ausgeführt wird, schneidet die größte Wiederholungen Gruppe off es finden kann aus der Anfang des Vektors, und dann läuft, bis sie alle weg sind.

Zuerst machen wir eine counter für die endgültige Ausgabe.

Als nächstes teilen wir x in jede Teilmenge beginnend von 1 in eine Liste, holding.

Dann finden wir alle Faktoren der Größe einer Gruppe, mit Ausnahme 1.

Dann das Schlimmste ist. Wir nehmen jede Teilmenge der größten Teilmenge und prüfen, ob sie der größten Teilmenge in ihrer Gruppe entspricht, nachdem sie die sinnvolle Anzahl von Malen wiederholt wurde.

findreps(x) 
[1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 
[37] 3 3 3 3 3 4 5 6 7 7 7 7 7 7 7 7 7 

Wenn Sie nicht-Wiederholungen wollen gruppiert werden, können wir ein wenig dplyr und tidyr verwenden:

library(dplyr) 
library(tidyr) 

z <- data.frame(x = x, y = findreps(x)) 

z %>% mutate(y = ifelse(duplicated(y) | rev(duplicated(rev(y))), y, NA), 
      holding = c(0, y[2:n()])) %>% 
     fill(holding) %>% 
     mutate(y = ifelse(is.na(y), holding +1, y)) %>% 
     select(-holding) 

Welche gibt:

[1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 7 7 7 7 7 7 7 7 
[53] 7 

Answer 2

Ich bin fast da, aber ich arbeite nicht für die vollen 100% und es wird spät (zzz). Zuerst der Code:

x <-c(rep(1:4, 5), rep(5:6, 3), rep(c(1, 4, 7), 5), rep(c(1, 5, 7), 1), rep(2:4, 3)) 

#The first break must be position 1 
Xbreaklist <- 1 

#We need a counter, a duplicate dataset 
counter <- 0 
xx <- x 

while (length(xx) > 0) { 
#first we extract a pattern by looking for the first repeated number 
Xpattern <- xx[1:(min(which(stri_duplicated(xx) == TRUE))-1)] 

#then we convert the vector and the pattern into a string 
XpatternS <- paste0(Xpattern, collapse="") 
xxS <- paste0(xx, collapse="") 

#then we extract all patterns and count them, multiply by length and add 1 
Xbreak <- 1 + (length(unlist(stri_extract_all_coll(xxS, XpatternS))) * length(Xpattern)) 

#break here if we reached the end 
if (Xbreak >= length(xx)) break 

# We add that to the list of breaks 
counter <- counter + Xbreak 
Xbreaklist <- c(Xbreaklist, counter) 

# then we remove the part of the list we're done with 
xx <- xx[(Xbreak):length(xx)] 
} 

Xbreaklist 
[1] 1 21 28 44 51 

Was ist los damit? Zwei Dinge:
1 Ein Muster, das nicht wiederholt wird, nimmt das erste Vorkommen des nächsten Musters mit: "121212 56 787878" wird geteilt als ("121212 5678 7878")
2 Wiederholungsmuster ("1212 5656 12 134") Dinge durcheinander bringen, weil stri_extract_all_coll sie alle herausnimmt und daher die Länge zu lang ist.

Answer 3

Dies ist eine unvollständige Antwort, aber dachte es besser als das Posten in einem Kommentar. Es kann andere dazu bringen, einen Weg zu finden, dies zu tun.

Meine Idee war, den Vektor in gleiche Teile der Größe N zu teilen. Dann zu überprüfen, ob der sukzessive Chunk ein Duplikat des vorherigen Chunks war. Ich habe das wahrscheinlich zu lange gemacht - ich bin mir sicher, dass es einen einfacheren Weg dafür geben muss.

Es scheint in Ordnung zu funktionieren und könnte die Grundlage für eine andere Möglichkeit sein, dies zu tun. Der Nachteil ist, dass es die Wiederholungen nicht aufnehmen kann, die nur einmal auftreten, z. "157".

xx <- split(x, ceiling(seq_along(x)/N)) #split vector into equal chunks of size N 
xx <- xx[-(length(xx))] #get rid of uneven splitting of last vector 

df <- do.call('rbind', xx) #bind together in a dataframe 

results<-NULL #loop to test if row is same as previous row (must be better way to do this) 
for(i in 2:nrow(df)-1) {results[[i]] <- df[i,]==df[i+1,] } 

results1 <- unlist(lapply(results, sum)) #count TRUEs in each result 
results1[results1<N]<-0 #make all not equal to size of chunk (N) equal to zero 

indices <- which(diff(results1)==-N)+1 #this is the first non-repeating group of N 
indicesall <- (indices*N)+1 #to find location of next non-repeating id