Find complete sets in a list using data.table

user_5440749 0
Viewed 54

Lets say I have the following list:

org <- list(1L, c(1L,2L), 2L, c(1L,3L), c(1L,2L,3L), c(2L,3L), 3L, 4L)
str(org)
#> List of 8
#>  $ : int 1
#>  $ : int [1:2] 1 2
#>  $ : int 2
#>  $ : int [1:2] 1 3
#>  $ : int [1:3] 1 2 3
#>  $ : int [1:2] 2 3
#>  $ : int 3
#>  $ : int 4

Now I would like to obtain the positions in the list with the complete sets. So in the example the positions 1,2,3,4,6,7 are all subsets of the 5th element in the list. The 8th element in the list is not a subset of other elements in the list. So, I would like to have returned the position of these elements. In this case: 5 and 8.

compl <- c(5, 8)

Can I easily achieve this using data.table?

Created on 2021-04-29 by the reprex package (v1.0.0)

data.table r
2 Answers

Here's a base R option :

#Define a function which identifies a complete set
complete_set <- function(x, y) all(x %in% y)
#Check each set with every other set
mat <- sapply(org, function(x) sapply(org, function(y) complete_set(x, y)))
#Turn diagonals to be FALSE
diag(mat) <- FALSE
#position of sets which are not complete
which(colSums(mat) == 0)
#[1] 5 8

This basically is a double loop (hence not the most efficient if the list is too big). It compares every element in the list (x) with every other element (y) and returns TRUE if the first element (x) completely exists in the second one (y). Since every element, completely exists with itself we manually turn them to FALSE using diag(mat) <- FALSE. Finally, we select only those elements that do not exist completely in any of the element in the list. (colSums(mat) == 0).

user_39629140

Edit - shortened it further Based on the explanation by dear mentor @Ronak, I also did it in purrr

org <- list(1L, c(1L,2L), 2L, c(1L,3L), c(1L,2L,3L), c(2L,3L), 3L, 4L)

library(purrr)

org[imap_int(org, ~ sum(sapply(org[-(.y)], FUN = function(xy) all(.x %in% xy)))) == 0]
#> [[1]]
#> [1] 1 2 3
#> 
#> [[2]]
#> [1] 4

#OR index only
ind <- imap_int(org, ~ sum(sapply(org[-(.y)], FUN = function(xy) all(.x %in% xy)))) == 0

seq_along(org)[ind]
#> [1] 5 8

Created on 2021-04-29 by the reprex package (v2.0.0)

user_28848590
Related