CODEWITHSUNDEEP
rlistvectorintersect
Jessica B
Jessica B

Reputation: 321

Minimum number of common elements from a list of multiple vectors

I have a list containing several vectors, e.g.:

ls=list(c("g1","g3","g6"),c("g1","g4"),c("g2","g5"),c("g2","g5"),c("g2"))

I want to capture the minimum number of elements so that I have at least one element from each vector.

So in this example, "g1" and "g2" because g1 captures vectors 1 and 2 and g2 captures vectors 1, 3, 4 and 5.

I've been looking at How to find common elements from multiple vectors? but it isn't quite the same question.

Upvotes: 1

Views: 456

Answers (1)

Roland
Roland

Reputation: 132676

Brute force:

ls <- list(c("g1","g3","g6"),c("g1","g4"),c("g2","g5"),c("g2","g5"),c("g2"))
#unique values:
vals <- unique(do.call(c,ls))
#matrix indicating in which list each value is present
valsin <- sapply(ls,function(x) as.integer(vals %in% x))
rownames(valsin) <- vals

#loop through numbers of values to take for combinations
for (i in seq_along(vals)) {

    cat(paste0(i,"\n"))
    #Do combinations fullfill condition?
    suff <- combn(seq_along(vals),i,FUN=function(x) {
      identical(colSums(valsin[x,,drop=FALSE]),rep(1,length(ls)))
    })
    if (sum(suff) > 0) {
      #combinations that fullfill condition
      res <- combn(vals,i)[,suff]
      #stop loop if condition has been fullfilled
      break
    }

}

res
#[1] "g1" "g2"

Upvotes: 1

Related Questions