Блог

Рассмотрим следующий список, где каждый элемент содержит наборы чисел.

 sets <- list(a=1:3, b=2:3, c=4:6, d=4:6, e=7)
  

Я хочу идентифицировать все наборы, которые являются правильными подмножествами другого набора в списке, таким образом, чтобы мой желаемый результат выглядел следующим образом…

 c(F,T,F,F,F)
  

Поскольку мои фактические наборы довольно велики, я не хочу, чтобы мне нужно было вычислять наборы мощности для каждого набора. У кого-нибудь есть идеи по поводу эффективного способа сделать это?

Это то, что я делал до сих пор, и это работает, но это не самый элегантный способ сделать это.

  truthtable <- bind_rows(lapply(X=sets, FUN=function(x, allsets){
  unlist(lapply(X=allsets, FUN=function(x,testset){
    return(all(x %in% testset) amp; !setequal(x, testset))
  }, testset=x))
}, allsets=sets))

apply(truthtable, 1, function(x){(all(!x))})
  

Я не знаю, откуда allsets взялось, но ваш общий подход выглядит нормально. Вот переработанная версия, использующая простой for цикл:

 is_proper_subset = function(x, y) {
  all(x %in% y) amp;amp; !setequal(x, y)
}

result = rep(NA, length(sets))
for (i in seq_along(sets)) {
  result[i] = any(sapply(sets[-i], is_proper_subset, x = sets[[i]]))
}
result
# [1] FALSE  TRUE FALSE FALSE FALSE
  

Чтобы ускорить операции с множествами, используйте бинарные диаграммы решений.

В зависимости от того, какие операции над наборами наборов вам нужны, вы можете выбрать различные варианты BSD. В самом общем случае используйте идентификатор каждого набора на терминальных узлах и не объединяйте терминальные узлы.

Существуют тысячи различных статей, где вы можете узнать, как их реализовать; по сравнению со списками и другими тривиальными структурами данных, для реализации BSD у вас есть множество различных способов сделать это, и вам потребуется еще некоторое умственное усилие, чтобы иметь возможность их использовать, но после того, как вы их поймете, вам понравится эта структура данных.

Это требует больших интеллектуальных усилий, чтобы понять это, но это будет выполняться действительно быстро, когда вы реализуете список множеств, наборы множеств (powerset), как вы хотите.