最小的列表覆盖数 [英] Minimal number of coverage of lists
问题描述
我有以下内容:
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组件,那么我想选择最大覆盖率.
I would like to find all the relevant p
that the unification of them will be the maximal components of dist
.
I this case the solution would be p1, p3, p5
.
I want to choose the minimal number of p
. In addition, in case there is no way to cover all the of dist component so I want to choose the maximal cover.
推荐答案
这是我尝试的解决方案.我已经尽我所能来矢量化/矩阵化它的速度足够快的希望.每个步骤都在注释中说明
Here is my attempted solution. I've tried as much I can to vectorize/matricize hope it's fast enough. Each step is explained in the comment
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,可以使用
In case you want to use quanteda, you can generate attribute_matrix
with
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
这篇关于最小的列表覆盖数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!