Keeping elements (from list of vectors) that do not have a proper subset within that list (in R)

user_13187091 0
Viewed 71

Proper subset: A proper subset S' of a set S is a subset that is strictly contained in S and so excludes S itself (note I am also excluding the empty set).

Suppose you have the following vectors in a list:

a = c(1,2)
b = c(1,3)
c = c(2,4)
d = c(1,2,3,4)
e = c(2,4,5)
f = c(1,2,3)

My aim is to keep only vectors which have no proper subset within the list, which in this example would be a, b and c. The following code is my solution,

possibilities = list(a,b,c,d,e,f)

final.list <- possibilities

for (i in possibilities) {
  for (j in rev(possibilities)) {
    if (all(i %in% j) & !all(j %in% i)) {
      final.list <- final.list[!(final.list %in% list(j))]
    } else {
      final.list <- final.list
    }
  }
}

which gives the intended output, though I am concerned with the scalability of this approach. Does anyone have an idea for a more efficient approach? Thanks!

* Note that for my true purpose the length of the possibilities list--and its sub-vectors--can grow quite large.

vector r set list
2 Answers

One purrr option could be:

map2(.x = possibilities,
     .y = seq_along(possibilities),
     ~ !any(map_lgl(possibilities[-.y], function(z) all(z %in% .x))))

[[1]]
[1] TRUE

[[2]]
[1] TRUE

[[3]]
[1] TRUE

[[4]]
[1] FALSE

[[5]]
[1] FALSE

[[6]]
[1] FALSE

To keep only the target vectors:

keep(possibilities,
     map2_lgl(.x = possibilities,
              .y = seq_along(possibilities),
              ~ !any(map_lgl(possibilities[-.y], function(z) all(z %in% .x)))))

[[1]]
[1] 1 2

[[2]]
[1] 1 3

[[3]]
[1] 2 4
user_59645570

Here is a base R option

final.list <- subset(
  possibilities,
  sapply(
    seq_along(possibilities),
    function(k) {
      !any(sapply(
        possibilities[-k],
        function(v) all(v %in% possibilities[[k]]) & length(v) < length(possibilities[[k]])
      ))
    }
  )
)

which gives

> final.list
[[1]]
[1] 1 2

[[2]]
[1] 1 3

[[3]]
[1] 2 4
user_121587570
Related