Для списка наборов: Как определить все элементы, которые являются подходящим подмножеством другого элемента списка?

Question

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

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) & !setequal(x, testset))
  }, testset=x))
}, allsets=sets))

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

Answer 1

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

is_proper_subset = function(x, y) {
  all(x %in% y) && !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

Answer 2

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

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

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

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