最少數量清單

Question

的覆蓋我有以下幾點：

dist<-c('att1','att2','att3','att4','att5','att6') 
p1<-c('att1','att5','att2') 
p2<-c('att5','att1','att4') 
p3<-c('att3','att4','att2') 
p4<-c('att1','att2','att3') 
p5<-c('att6') 

我想找到所有相關p是他們的統一將是dist的最大組成部分。 我這種情況下的解決方案將是p1, p3, p5。 我想選擇p的最小數量。另外，如果無法覆蓋所有的dist組件，所以我想選擇最大覆蓋。

Answer 1

這是我的嘗試解決方案。我已儘可能多地嘗試矢量化/預測速度足夠快。每一步都在評論

library(qdapTools) 
library(dplyr) 
library(data.table) 
## generate matrix of attributes 
grid_matrix <- do.call(CJ, rep(list(1:0), 5)) %>% as.matrix 
attribute_matrix 
## att1 att2 att3 att4 att5 att6 
## 1 1 1 0 0 1 0 
## 2 1 0 0 1 1 0 
## 3 0 1 1 1 0 0 
## 4 1 1 1 0 0 0 
## 5 0 0 0 0 0 1 

## create a grid of combination of matrix 
grid_matrix <- do.call(CJ, rep(list(1:0), 5)) %>% as.matrix 
colnames(grid_matrix) <- paste0("p", 1:5) 

## check whether each combination has all attribute presented 
combin_all_element_present <- rowSums(grid_matrix %*% attribute_matrix > 0) %>% 
    `==`(., ncol(attribute_matrix)) 

combin_all_element_present 
## [1] TRUE TRUE TRUE FALSE TRUE TRUE FALSE FALSE TRUE TRUE TRUE 
## [12] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE 
## [23] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE 

## generate a submatrix which satisfy the condition 
grid_matrix_sub <- grid_matrix[combin_all_element_present, ] 
## find the combinations with minumun number of p 
grid_matrix_sub[rowSums(grid_matrix_sub) == min(rowSums(grid_matrix_sub)), ] 
##  p1 p2 p3 p4 p5 
## [1,] 0 1 0 1 1 
## [2,] 0 1 1 0 1 
## [3,] 1 0 1 0 1 

註解釋

在要使用quanteda情況下，可以產生與attribute_matrix

library(quanteda) 
attribute_matrix <- lapply(list(p1, p2, p3, p4, p5), function(x) paste(x, collapse = ' ')) %>% 
    unlist %>% tokens %>% dfm %>% as.matrix 
attribute_matrix 
##  features 
## docs att1 att5 att2 att4 att3 att6 
## text1 1 1 1 0 0 0 
## text2 1 1 0 1 0 0 
## text3 0 0 1 1 1 0 
## text4 1 0 1 0 1 0 
## text5 0 0 0 0 0 1