Как вычислить все наборы мощности с кардинальностью не более K?

Question

Я установил $ S $ с количеством элементов $ M $.Я хотел бы создать все powerset из $ S $ с максимальным количеством элементов $ K $, где $ K \ le M $.Я использовал $ R $ для создания блоков питания, но он не дает возможности ограничить его упомянутым случаем.Поскольку размер $ S $ действительно велик (500), для моей задачи мне просто нужно вычислить все подмножества с максимальным количеством элементов 5. Может ли кто-нибудь помочь мне сделать это в R?

Answer 1

С | S |= 500 К не сможет быть очень большим.Для k = 0, 1, 2, 3, 4, 5 это количество подмножеств, имеющих размер не более k:

cumsum(sapply(0:5, choose, n = 500))
## [1]            1          501       125251     20833751   2593864876 257838552476

Теперь обратимся к примечанию кода, что combn(x = S, m = i, simplify = FALSE) дает все подмножестваразмером i так:

#  test data
S <- head(letters, 4)
k <- 2

subsets_k <- do.call("c", lapply(0:k, combn, x = S, simplify = FALSE))

, давая все подмножества 0, 1 или k = 2 элементов:

> subsets_k
[[1]]
character(0)

[[2]]
[1] "a"

[[3]]
[1] "b"

[[4]]
[1] "c"

[[5]]
[1] "d"

[[6]]
[1] "a" "b"

[[7]]
[1] "a" "c"

[[8]]
[1] "a" "d"

[[9]]
[1] "b" "c"

[[10]]
[1] "b" "d"

[[11]]
[1] "c" "d"

или мы можем представить их как символьный вектор запятойотдельные элементы:

sapply(subsets_k, toString)
## [1] ""     "a"    "b"    "c"    "d"    "a, b" "a, c" "a, d" "b, c" "b, d" "c, d"

или напрямую:

unlist(sapply(0:k, function(i) combn(S, i, FUN = toString)))
## [1] ""     "a"    "b"    "c"    "d"    "a, b" "a, c" "a, d" "b, c" "b, d" "c, d"