How to compute all power sets with cardinality at most K?
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?
r
asked Nov 26 '18 at 23:51
user2806363user2806363
76031432
add a comment |
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?
r
asked Nov 26 '18 at 23:51
user2806363user2806363
76031432
1
Rather than all power sets (isn't there only one?), perhaps you mean all collections of subsets?
– Julius Vainora
Nov 27 '18 at 0:07
@JuliusVainora, both are same
– user2806363
Nov 27 '18 at 0:19
Then it must be some nonstandard definition (mathworld.wolfram.com/PowerSet.html)
– Julius Vainora
Nov 27 '18 at 0:23
You mean subset, not powerset
– Hong Ooi
Nov 27 '18 at 1:06
add a comment |
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?
r
asked Nov 26 '18 at 23:51
user2806363user2806363
76031432
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?
r
r
asked Nov 26 '18 at 23:51
user2806363user2806363
76031432
asked Nov 26 '18 at 23:51
user2806363user2806363
76031432
asked Nov 26 '18 at 23:51
user2806363user2806363
76031432
asked Nov 26 '18 at 23:51
user2806363user2806363
76031432
asked Nov 26 '18 at 23:51
user2806363user2806363
76031432
76031432
1
Rather than all power sets (isn't there only one?), perhaps you mean all collections of subsets?
– Julius Vainora
Nov 27 '18 at 0:07
@JuliusVainora, both are same
– user2806363
Nov 27 '18 at 0:19
Then it must be some nonstandard definition (mathworld.wolfram.com/PowerSet.html)
– Julius Vainora
Nov 27 '18 at 0:23
You mean subset, not powerset
– Hong Ooi
Nov 27 '18 at 1:06
add a comment |
1
Rather than all power sets (isn't there only one?), perhaps you mean all collections of subsets?
– Julius Vainora
Nov 27 '18 at 0:07
@JuliusVainora, both are same
– user2806363
Nov 27 '18 at 0:19
Then it must be some nonstandard definition (mathworld.wolfram.com/PowerSet.html)
– Julius Vainora
Nov 27 '18 at 0:23
You mean subset, not powerset
– Hong Ooi
Nov 27 '18 at 1:06
1
1
Rather than all power sets (isn't there only one?), perhaps you mean all collections of subsets?
– Julius Vainora
Nov 27 '18 at 0:07
Rather than all power sets (isn't there only one?), perhaps you mean all collections of subsets?
– Julius Vainora
Nov 27 '18 at 0:07
@JuliusVainora, both are same
– user2806363
Nov 27 '18 at 0:19
@JuliusVainora, both are same
– user2806363
Nov 27 '18 at 0:19
Then it must be some nonstandard definition (mathworld.wolfram.com/PowerSet.html)
– Julius Vainora
Nov 27 '18 at 0:23
Then it must be some nonstandard definition (mathworld.wolfram.com/PowerSet.html)
– Julius Vainora
Nov 27 '18 at 0:23
You mean subset, not powerset
– Hong Ooi
Nov 27 '18 at 1:06
You mean subset, not powerset
– Hong Ooi
Nov 27 '18 at 1:06
add a comment |
1 Answer
1
active
oldest
votes
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"
answered Nov 27 '18 at 0:57
G. GrothendieckG. Grothendieck
149k10132236
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53490809%2fhow-to-compute-all-power-sets-with-cardinality-at-most-k%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
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"
answered Nov 27 '18 at 0:57
G. GrothendieckG. Grothendieck
149k10132236
add a comment |
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"
answered Nov 27 '18 at 0:57
G. GrothendieckG. Grothendieck
149k10132236
add a comment |
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"
answered Nov 27 '18 at 0:57
G. GrothendieckG. Grothendieck
149k10132236
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"
answered Nov 27 '18 at 0:57
G. GrothendieckG. Grothendieck
149k10132236
edited Nov 27 '18 at 1:13
answered Nov 27 '18 at 0:57
G. GrothendieckG. Grothendieck
149k10132236
answered Nov 27 '18 at 0:57
G. GrothendieckG. Grothendieck
149k10132236
answered Nov 27 '18 at 0:57
G. GrothendieckG. Grothendieck
149k10132236
149k10132236
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53490809%2fhow-to-compute-all-power-sets-with-cardinality-at-most-k%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Rather than all power sets (isn't there only one?), perhaps you mean all collections of subsets?
– Julius Vainora
Nov 27 '18 at 0:07
@JuliusVainora, both are same
– user2806363
Nov 27 '18 at 0:19
Then it must be some nonstandard definition (mathworld.wolfram.com/PowerSet.html)
– Julius Vainora
Nov 27 '18 at 0:23
You mean subset, not powerset
– Hong Ooi
Nov 27 '18 at 1:06