How to return the unique elements between vectors while retaining the source vector of these unique elements?

user_14531760 0
Viewed 125

For example, I have 5 vectors in a list:

A <- c(1,2,3,4,5)

B <- c(1,2,3,4,5,6)

C <- c(5,6,7,8,9)

D <- c(8,9)

In reality I have 100s of these vectors but I only gave 5 vectors for reproducibility. My goal is to:

  1. Identify the unique elements coming from the vectors. For example, vector A shouldn't return anything because all of its elements are part of vector B, however vector B does contribute with an extra unique element and that is 6. Vector C should give me 7,8,9 since c(5,6) were already included in vector B. Vector D should return nothing because all of its elements are part of C
  2. recognize which element is unique from which vector
  3. Find which vectors are subsets of other bigger vectors. For example, vector D is a subset of C and vector A is a subset of vector B.

So far the only solution I've found was:

Reduce(setdiff, list("my_vectors"))

But it doesn't allow me to recognize which element is unique from which vector. For example, Reduce(setdiff, list(A,B)) would return 6, but I would have no idea where the 6 came from ( A or B)?

My difficulty is in this being a large scale problem, I don't have 5 vectors only, I have 100s of them so I can't figure out a sustainable solution. Any tips are appreciated.

Edit: my vectors are in a list

vector data-mining r unique list
4 Answers

A first naive approach would be a for-loop, just to have a working solution. The function returns a list with the unqiue elements and a dataframe, describing from which vector in the vectorList the unique elements (first appereance) are coming from.

A <- c(1,2,3,4,5)
B <- c(1,2,3,4,5,6)
C <- c(5,6,7,8,9)
D <- c(8,9)

vectorList <- list(A,B,C,D)

ff <- function(vectorList) {
  uniques <- unique(vectorList[[1]])
  comingFromDf <- data.frame(values=uniques)
  comingFromDf$source <- 1
  
  for(k in 2:length(vectorList)) {
    vec <- vectorList[[k]]
    newUniques <- vec[!(vec %in% uniques)]
    if(length(newUniques)) {
      newUniques <- unique(newUniques)
      toAdd <- data.frame(values=newUniques)
      toAdd$source <- k
      comingFromDf <- rbind(comingFromDf,toAdd)
      uniques <- c(uniques,newUniques)
    }
  }
  
  list(uniqueElements = uniques,
       comingFromInfo = comingFromDf)
}

ff(vectorList)

I don't know how performant you need the function to be, but even with 200 vectors of length 1000 it seems to be quit fast (I don't know about your dimensions):

bigVectorList <- lapply(1:200, function(k) {
  sample(1:1e6,1000)
})

microbenchmark::microbenchmark(ff(bigVectorList),times=10)
#Unit: milliseconds
#              expr      min       lq     mean   median      uq      max neval
#ff(bigVectorList) 619.5148 624.8351 639.7535 633.2326 647.118 685.0387    10

On my machine, it took a bit more than half a second, maybe thats enough for you. Since the function only includes vectors and a dataframe, it would be quit easy to re-implement it in C++ and using Rcpp. This should be much faster than the for-loop implementation in R. Moreover, you can consider using the accumulate-argument in the Reduce-function to save the intermediate calculation-results.

user_143164880

Assume your data is stored like this:

my_vectors <- list(
  A = c(1,2,3,4,5),
  B = c(1,2,3,4,5,6),
  C = c(5,6,7,8,9),
  D = c(8,9)
)

If you use accumulate = TRUE to the call of Reduce, you get every intermediate result as well. We can use this together with union to build up the total set step by step (note that I set init = c() to make sure we start empty):

acc <- Reduce(union, my_vectors, init = c(), accumulate = T)

Then, we can take the setdiff of every item with this built-up list.

lapply(1:length(my_vectors), function(i) setdiff(my_vectors[[i]], acc[[i]]))

This gives

[[1]]
[1] 1 2 3 4 5

[[2]]
[1] 6

[[3]]
[1] 7 8 9

[[4]]
numeric(0)

You can apply the names of my_vectors later if you want.

user_10622250

Here is a tidyverse solution.

lag(accumulate(l, union)) keeps track of all the elements seen so far. The difference between this and the original list yields the newly seen elements.

library(tidyverse)

l <- lst(A, B, C, D)

map2(l, lag(accumulate(l, union)), setdiff)
#> $A
#> [1] 1 2 3 4 5
#> 
#> $B
#> [1] 6
#> 
#> $C
#> [1] 7 8 9
#> 
#> $D
#> numeric(0)
Here is an answer to your other question about finding which vectors are subsets of other bigger vectors.

expand_grid will get all combinations of the vectors. Filter this to find which vector is a subset of any other vector.

l %>%
  enframe() %>%
  expand_grid(a = ., b = .) %>%
  filter(
    a$name != b$name,
    map2_lgl(a$value, b$value, ~all(.x %in% .y))
  ) %>%
  transmute(this_vector = a$name, is_a_subset_of_this_vector = b$name)
#> # A tibble: 2 x 2
#>   this_vector is_a_subset_of_this_vector
#>   <chr>       <chr>                     
#> 1 A           B                         
#> 2 D           C
user_17519610

Here you only have one truly unique element which is 7 in C. The below will return the unique elements as well as their memberships

mylist <- list("A"=A,"B"=B,"C"=C,"D"=D) #better for 100's of vectors
myres <- !unlist(lapply(1:length(mylist), function(x) unlist(mylist[x]) %in% unlist(mylist[-x])))
result <- as.numeric(unlist(mylist)[myres])
member <- sapply(mylist, function(x) result %in% x)
membername <- names(mylist[member])
result
membername
> result
 7 
> membername
[1] "C"
user_52242360
Related