r - How to compute all power sets with cardinality at most K?

Question

I have set $S$ with the cardinality of $M$. I would like to create all powerset of $S$ with at most cardinality of $K$ where $K le M$. I used $R$ to create powersets, but it does not provide an option to constrain it to the mentioned case. Since size of $S$ is really large (500), for my problem, I just need to compute all subsets with cardinality at most 5. Can someone help me to do this in R?

Answer 1

With |S| = 500 k won't be able to be very large. For k = 0, 1, 2, 3, 4, 5 this is how many subsets there are having size of at most k:

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

Now turning to the code note that combn(x = S, m = i, simplify = FALSE) gives all subsets of size i so:

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

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

giving all subsets of 0, 1 or k=2 elements:

> 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"

or we can represent these as a character vector of comma-separated elements:

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

or directly:

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"