Làm thế nào để tìm số liên tiếp trong nhiều mảng?

Question

tôi ngay lập tức đưa ra một ví dụ, bây giờ giả sử tôi có 3 mảng a, b, c như

a = c(3,5) 
b = c(6,1,8,7) 
c = c(4,2,9) 

tôi phải có khả năng trích xuất ba liên tiếp trong đó có tôi, e.,

c(1,2,3),c(4,5,6) 

Nhưng đây chỉ là một ví dụ, tôi sẽ có một tập dữ liệu lớn hơn với thậm chí nhiều hơn 10 mảng, do đó phải có khả năng tìm chuỗi liên tiếp có độ dài mười.

Vì vậy, bất kỳ ai cũng có thể cung cấp thuật toán, thường tìm chuỗi liên tiếp có độ dài 'n' trong mảng 'n'.

Tôi đang thực sự làm công cụ này trong R, do đó, nó thích hợp hơn nếu bạn cung cấp mã của bạn bằng R. Tuy nhiên, thuật toán từ bất kỳ ngôn ngữ nào cũng được hoan nghênh hơn.

Answer 1

Sắp xếp lại dữ liệu đầu tiên vào danh sách chứa giá trị và số mảng. Sắp xếp danh sách; bạn muốn có ai lấy cái gì như:

1-2 
2-3 
3-1 (i.e. " there' s a three in array 1") 
4-3 
5-1 
6-2 
7-2 
8-2 
9-3 

Sau đó, vòng lặp trong danh sách, kiểm tra xem có thực sự là n số thứ tự, sau đó kiểm tra xem những có số mảng khác nhau

Answer 2

Đây là một cách tiếp cận. Điều này giả định không có sự phá vỡ trong chuỗi các quan sát về số lượng các nhóm. Đây là dữ liệu.

N <- 3 
a <- c(3,5) 
b <- c(6,1,8,7) 
c <- c(4,2,9) 

Sau đó, tôi kết hợp chúng lại với nhau và trật tự của các quan sát

dd <- lattice::make.groups(a,b,c) 
dd <- dd[order(dd$data),] 

Bây giờ tôi tìm kiếm hàng trong bảng này, nơi cả ba nhóm được đại diện

idx <- apply(embed(as.numeric(dd$which),N), 1, function(x) { 
    length(unique(x))==N 
}) 

Sau đó, chúng ta có thể thấy ba số với

lapply(which(idx), function(i) { 
    dd[i:(i+N-1),] 
}) 

# [[1]] 
# data which 
# b2 1  b 
# c2 2  c 
# a1 3  a 
# 
# [[2]] 
# data which 
# c1 4  c 
# a2 5  a 
# b1 6  b 

Answer 3

Dưới đây là một phương pháp brute force với expand.grid và ba vectơ như trong ví dụ

# get all combinations 
df <- expand.grid(a,b,c) 

Sử dụng combn để tính toán sự khác biệt cho mỗi sự kết hợp cặp.

# get all parwise differences 
myDiffs <- combn(names(df), 2, FUN=function(x) abs(x[1]-x[2])) 

# subset data using `rowSums` and `which` 
df[which(rowSums(myDiffs == 1) == ncol(myDiffs)-1), ] 

df[which(rowSums(myDiffs == 1) == ncol(myDiffs)-1), ] 
    Var1 Var2 Var3 
2  5 6 4 
11 3 1 2 

Answer 4

Tôi đã bị tấn cùng một chức năng ít đệ quy đó sẽ tìm tất cả các bộ ba liên tiếp giữa nhiều vectơ khi bạn vượt qua nó (cần phải vượt qua ít nhất ba). Nó có lẽ là một chút thô, nhưng dường như làm việc.

Hàm sử dụng dấu ba chấm, ..., để chuyển đối số. Do đó, sẽ cần nhiều đối số (ví dụ: vectơ số) mà bạn cung cấp và đặt chúng trong danh sách items. Sau đó, giá trị nhỏ nhất trong mỗi vector được truyền đi, cùng với chỉ số của nó.

Sau đó, phân của các vectơ tương ứng với bộ ba nhỏ nhất được tạo và lặp lại thông qua sử dụng vòng lặp for(), trong đó các giá trị đầu ra được chuyển đến vector đầu ra out.Các vectơ đầu vào trong items được cắt tỉa và truyền lại thành hàm theo kiểu đệ quy. Chỉ khi tất cả vectơ là NA, nghĩa là không còn giá trị nào trong vectơ, hàm trả về kết quả cuối cùng.

library(magrittr) 

# define function to find the triplets 
tripl <- function(...){ 
    items <- list(...) 

    # find the smallest number in each passed vector, along with its index 
    # output is a matrix of n-by-2, where n is the number of passed arguments 
    triplet.id <- lapply(items, function(x){ 
    if(is.na(x) %>% prod) id <- c(NA, NA) 
    else id <- c(which(x == min(x)), x[which(x == min(x))]) 
    }) %>% unlist %>% matrix(., ncol=2, byrow=T) 


    # find the smallest triplet from the passed vectors 
    index <- order(triplet.id[,2])[1:3] 
    # create empty vector for output 
    out <- vector() 

    # go through the smallest triplet's indices 
    for(i in index){ 
    # .. append the coresponding item from the input vector to the out vector 
    # .. and remove the value from the input vector 
    if(length(items[[i]]) == 1) { 
     out <- append(out, items[[i]]) 
     # .. if the input vector has no value left fill with NA 
     items[[i]] <- NA 
    } 
    else { 
     out <- append(out, items[[i]][triplet.id[i,1]]) 
     items[[i]] <- items[[i]][-triplet.id[i,1]] 
    } 
    } 

    # recurse until all vectors are empty (NA) 
    if(!prod(unlist(is.na(items)))) out <- append(list(out), 
               do.call("tripl", c(items), quote = F)) 
    else(out <- list(out)) 

    # return result 
    return(out) 
} 

Chức năng có thể được gọi bằng cách truyền các vectơ đầu vào làm đối số.

# input vectors 
a = c(3,5) 
b = c(6,1,8,7) 
c = c(4,2,9) 

# find all the triplets using our function 
y <- tripl(a,b,c) 

Kết quả là danh sách chứa tất cả thông tin cần thiết, mặc dù không có thứ tự.

print(y) 
# [[1]] 
# [1] 1 2 3 
# 
# [[2]] 
# [1] 4 5 6 
# 
# [[3]] 
# [1] 7 9 NA 
# 
# [[4]] 
# [1] 8 NA NA 

đặt hàng tất cả mọi thứ có thể được thực hiện bằng sapply():

# put everything in order 
sapply(y, function(x){x[order(x)]}) %>% t 
#  [,1] [,2] [,3] 
# [1,] 1 2 3 
# [2,] 4 5 6 
# [3,] 7 9 NA 
# [4,] 8 NA NA 

Có điều là, rằng nó sẽ chỉ sử dụng một giá trị mỗi vector để tìm ba. Do đó, sẽ không tìm thấy bộ ba liên tiếp c(6,7,8) trong số các ví dụ: c(6,7,11), c(8,9,13) và c(10,12,14). Trong trường hợp này, nó sẽ trả về c(6,8,10) (xem bên dưới).

a<-c(6,7,11) 
b<-c(8,9,13) 
c<-c(10,12,14) 

y <- tripl(a,b,c) 
sapply(y, function(x){x[order(x)]}) %>% t 
#  [,1] [,2] [,3] 
# [1,] 6 8 10 
# [2,] 7 9 12 
# [3,] 11 13 14