count number of partitions of a set with n elements into k subsets
up vote
6
down vote
favorite
This program is for count number of partitions of a set with n elements into k subsets I am confusing here return k*countP(n-1, k) + countP(n-1, k-1);
can some one explain what is happening here?
why we are multiplying with k?
NOTE->I know this is not the best way to calculate number of partitions that would be DP
// A C++ program to count number of partitions
// of a set with n elements into k subsets
#include<iostream>
using namespace std;
// Returns count of different partitions of n
// elements in k subsets
int countP(int n, int k)
{
// Base cases
if (n == 0 || k == 0 || k > n)
return 0;
if (k == 1 || k == n)
return 1;
// S(n+1, k) = k*S(n, k) + S(n, k-1)
return k*countP(n-1, k) + countP(n-1, k-1);
}
// Driver program
int main()
{
cout << countP(3, 2);
return 0;
}
c++ algorithm combinatorics
New contributor
add a comment |
up vote
6
down vote
favorite
This program is for count number of partitions of a set with n elements into k subsets I am confusing here return k*countP(n-1, k) + countP(n-1, k-1);
can some one explain what is happening here?
why we are multiplying with k?
NOTE->I know this is not the best way to calculate number of partitions that would be DP
// A C++ program to count number of partitions
// of a set with n elements into k subsets
#include<iostream>
using namespace std;
// Returns count of different partitions of n
// elements in k subsets
int countP(int n, int k)
{
// Base cases
if (n == 0 || k == 0 || k > n)
return 0;
if (k == 1 || k == n)
return 1;
// S(n+1, k) = k*S(n, k) + S(n, k-1)
return k*countP(n-1, k) + countP(n-1, k-1);
}
// Driver program
int main()
{
cout << countP(3, 2);
return 0;
}
c++ algorithm combinatorics
New contributor
add a comment |
up vote
6
down vote
favorite
up vote
6
down vote
favorite
This program is for count number of partitions of a set with n elements into k subsets I am confusing here return k*countP(n-1, k) + countP(n-1, k-1);
can some one explain what is happening here?
why we are multiplying with k?
NOTE->I know this is not the best way to calculate number of partitions that would be DP
// A C++ program to count number of partitions
// of a set with n elements into k subsets
#include<iostream>
using namespace std;
// Returns count of different partitions of n
// elements in k subsets
int countP(int n, int k)
{
// Base cases
if (n == 0 || k == 0 || k > n)
return 0;
if (k == 1 || k == n)
return 1;
// S(n+1, k) = k*S(n, k) + S(n, k-1)
return k*countP(n-1, k) + countP(n-1, k-1);
}
// Driver program
int main()
{
cout << countP(3, 2);
return 0;
}
c++ algorithm combinatorics
New contributor
This program is for count number of partitions of a set with n elements into k subsets I am confusing here return k*countP(n-1, k) + countP(n-1, k-1);
can some one explain what is happening here?
why we are multiplying with k?
NOTE->I know this is not the best way to calculate number of partitions that would be DP
// A C++ program to count number of partitions
// of a set with n elements into k subsets
#include<iostream>
using namespace std;
// Returns count of different partitions of n
// elements in k subsets
int countP(int n, int k)
{
// Base cases
if (n == 0 || k == 0 || k > n)
return 0;
if (k == 1 || k == n)
return 1;
// S(n+1, k) = k*S(n, k) + S(n, k-1)
return k*countP(n-1, k) + countP(n-1, k-1);
}
// Driver program
int main()
{
cout << countP(3, 2);
return 0;
}
c++ algorithm combinatorics
c++ algorithm combinatorics
New contributor
New contributor
edited 52 mins ago
New contributor
asked 1 hour ago
godse121
344
344
New contributor
New contributor
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
up vote
2
down vote
Each countP
call implicitly considers a single element in the set, lets call it A.
The countP(n-1, k-1)
term comes from the case where A is in a set by itself. In this case, we just have to count how many ways there are to partition all the other elements (N-1) into (K-1) subsets, since A takes up one subset by itself.
The k*countP(n-1, k)
term, then, comes from the case where A is not in a set by itself. So we figure out the number of ways of partitioning all the other (N-1) values into K subsets, and multiply by K because there are K possible subsets we could add A to.
For example, consider the set [A,B,C,D]
, with K=2
.
The first case, countP(n-1, k-1)
, describes the following situation:
{A, BCD}
The second case, k*countP(n-1, k)
, describes the following cases:
2*({BC,D}, {BD,C}, {B,CD})
Or:
{ABC,D}, {ABD,C}, {AB,CD}, {BC,AD}, {BD,AC}, {B,ACD}
add a comment |
up vote
2
down vote
Based on This a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets. So the total number of partitions of an n-element set is the Bell number which is calculated like below:
Bell number formula
Hence if you want to convert the formula to a recursive function it will be like:
k*countP(n-1,k) + countP(n-1, k-1);
New contributor
add a comment |
up vote
1
down vote
How do we get countP(n,k)
? Assuming that we have devided previous n-1
element into a certain number of partions, and now we have the n-th element, and we try to make k
partition.
we have two option for this:
either
- we have devided the previous
n-1
elements intok
partions(we havecountP(n-1, k)
ways of doing this), and we put this n-th element into one of these partions(we havek
choices). So we havek*countP(n-1, k)
.
or:
- we divide previous
n-1
elements intok-1
partition(we havecountP(n-1, k-1);
ways of doing this), and we make the n-th element a single partion to achieve ak
partition(we only have 1 choice: putting it seperately). So we havecountP(n-1, k-1);
.
So we sum them up and get the result.
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',
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
});
}
});
godse121 is a new contributor. Be nice, and check out our Code of Conduct.
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%2f53799915%2fcount-number-of-partitions-of-a-set-with-n-elements-into-k-subsets%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Each countP
call implicitly considers a single element in the set, lets call it A.
The countP(n-1, k-1)
term comes from the case where A is in a set by itself. In this case, we just have to count how many ways there are to partition all the other elements (N-1) into (K-1) subsets, since A takes up one subset by itself.
The k*countP(n-1, k)
term, then, comes from the case where A is not in a set by itself. So we figure out the number of ways of partitioning all the other (N-1) values into K subsets, and multiply by K because there are K possible subsets we could add A to.
For example, consider the set [A,B,C,D]
, with K=2
.
The first case, countP(n-1, k-1)
, describes the following situation:
{A, BCD}
The second case, k*countP(n-1, k)
, describes the following cases:
2*({BC,D}, {BD,C}, {B,CD})
Or:
{ABC,D}, {ABD,C}, {AB,CD}, {BC,AD}, {BD,AC}, {B,ACD}
add a comment |
up vote
2
down vote
Each countP
call implicitly considers a single element in the set, lets call it A.
The countP(n-1, k-1)
term comes from the case where A is in a set by itself. In this case, we just have to count how many ways there are to partition all the other elements (N-1) into (K-1) subsets, since A takes up one subset by itself.
The k*countP(n-1, k)
term, then, comes from the case where A is not in a set by itself. So we figure out the number of ways of partitioning all the other (N-1) values into K subsets, and multiply by K because there are K possible subsets we could add A to.
For example, consider the set [A,B,C,D]
, with K=2
.
The first case, countP(n-1, k-1)
, describes the following situation:
{A, BCD}
The second case, k*countP(n-1, k)
, describes the following cases:
2*({BC,D}, {BD,C}, {B,CD})
Or:
{ABC,D}, {ABD,C}, {AB,CD}, {BC,AD}, {BD,AC}, {B,ACD}
add a comment |
up vote
2
down vote
up vote
2
down vote
Each countP
call implicitly considers a single element in the set, lets call it A.
The countP(n-1, k-1)
term comes from the case where A is in a set by itself. In this case, we just have to count how many ways there are to partition all the other elements (N-1) into (K-1) subsets, since A takes up one subset by itself.
The k*countP(n-1, k)
term, then, comes from the case where A is not in a set by itself. So we figure out the number of ways of partitioning all the other (N-1) values into K subsets, and multiply by K because there are K possible subsets we could add A to.
For example, consider the set [A,B,C,D]
, with K=2
.
The first case, countP(n-1, k-1)
, describes the following situation:
{A, BCD}
The second case, k*countP(n-1, k)
, describes the following cases:
2*({BC,D}, {BD,C}, {B,CD})
Or:
{ABC,D}, {ABD,C}, {AB,CD}, {BC,AD}, {BD,AC}, {B,ACD}
Each countP
call implicitly considers a single element in the set, lets call it A.
The countP(n-1, k-1)
term comes from the case where A is in a set by itself. In this case, we just have to count how many ways there are to partition all the other elements (N-1) into (K-1) subsets, since A takes up one subset by itself.
The k*countP(n-1, k)
term, then, comes from the case where A is not in a set by itself. So we figure out the number of ways of partitioning all the other (N-1) values into K subsets, and multiply by K because there are K possible subsets we could add A to.
For example, consider the set [A,B,C,D]
, with K=2
.
The first case, countP(n-1, k-1)
, describes the following situation:
{A, BCD}
The second case, k*countP(n-1, k)
, describes the following cases:
2*({BC,D}, {BD,C}, {B,CD})
Or:
{ABC,D}, {ABD,C}, {AB,CD}, {BC,AD}, {BD,AC}, {B,ACD}
answered 45 mins ago
wowserx
39418
39418
add a comment |
add a comment |
up vote
2
down vote
Based on This a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets. So the total number of partitions of an n-element set is the Bell number which is calculated like below:
Bell number formula
Hence if you want to convert the formula to a recursive function it will be like:
k*countP(n-1,k) + countP(n-1, k-1);
New contributor
add a comment |
up vote
2
down vote
Based on This a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets. So the total number of partitions of an n-element set is the Bell number which is calculated like below:
Bell number formula
Hence if you want to convert the formula to a recursive function it will be like:
k*countP(n-1,k) + countP(n-1, k-1);
New contributor
add a comment |
up vote
2
down vote
up vote
2
down vote
Based on This a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets. So the total number of partitions of an n-element set is the Bell number which is calculated like below:
Bell number formula
Hence if you want to convert the formula to a recursive function it will be like:
k*countP(n-1,k) + countP(n-1, k-1);
New contributor
Based on This a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets. So the total number of partitions of an n-element set is the Bell number which is calculated like below:
Bell number formula
Hence if you want to convert the formula to a recursive function it will be like:
k*countP(n-1,k) + countP(n-1, k-1);
New contributor
New contributor
answered 35 mins ago
Alireza.N
212
212
New contributor
New contributor
add a comment |
add a comment |
up vote
1
down vote
How do we get countP(n,k)
? Assuming that we have devided previous n-1
element into a certain number of partions, and now we have the n-th element, and we try to make k
partition.
we have two option for this:
either
- we have devided the previous
n-1
elements intok
partions(we havecountP(n-1, k)
ways of doing this), and we put this n-th element into one of these partions(we havek
choices). So we havek*countP(n-1, k)
.
or:
- we divide previous
n-1
elements intok-1
partition(we havecountP(n-1, k-1);
ways of doing this), and we make the n-th element a single partion to achieve ak
partition(we only have 1 choice: putting it seperately). So we havecountP(n-1, k-1);
.
So we sum them up and get the result.
add a comment |
up vote
1
down vote
How do we get countP(n,k)
? Assuming that we have devided previous n-1
element into a certain number of partions, and now we have the n-th element, and we try to make k
partition.
we have two option for this:
either
- we have devided the previous
n-1
elements intok
partions(we havecountP(n-1, k)
ways of doing this), and we put this n-th element into one of these partions(we havek
choices). So we havek*countP(n-1, k)
.
or:
- we divide previous
n-1
elements intok-1
partition(we havecountP(n-1, k-1);
ways of doing this), and we make the n-th element a single partion to achieve ak
partition(we only have 1 choice: putting it seperately). So we havecountP(n-1, k-1);
.
So we sum them up and get the result.
add a comment |
up vote
1
down vote
up vote
1
down vote
How do we get countP(n,k)
? Assuming that we have devided previous n-1
element into a certain number of partions, and now we have the n-th element, and we try to make k
partition.
we have two option for this:
either
- we have devided the previous
n-1
elements intok
partions(we havecountP(n-1, k)
ways of doing this), and we put this n-th element into one of these partions(we havek
choices). So we havek*countP(n-1, k)
.
or:
- we divide previous
n-1
elements intok-1
partition(we havecountP(n-1, k-1);
ways of doing this), and we make the n-th element a single partion to achieve ak
partition(we only have 1 choice: putting it seperately). So we havecountP(n-1, k-1);
.
So we sum them up and get the result.
How do we get countP(n,k)
? Assuming that we have devided previous n-1
element into a certain number of partions, and now we have the n-th element, and we try to make k
partition.
we have two option for this:
either
- we have devided the previous
n-1
elements intok
partions(we havecountP(n-1, k)
ways of doing this), and we put this n-th element into one of these partions(we havek
choices). So we havek*countP(n-1, k)
.
or:
- we divide previous
n-1
elements intok-1
partition(we havecountP(n-1, k-1);
ways of doing this), and we make the n-th element a single partion to achieve ak
partition(we only have 1 choice: putting it seperately). So we havecountP(n-1, k-1);
.
So we sum them up and get the result.
edited 14 mins ago
answered 44 mins ago
ZhaoGang
1,004914
1,004914
add a comment |
add a comment |
godse121 is a new contributor. Be nice, and check out our Code of Conduct.
godse121 is a new contributor. Be nice, and check out our Code of Conduct.
godse121 is a new contributor. Be nice, and check out our Code of Conduct.
godse121 is a new contributor. Be nice, and check out our Code of Conduct.
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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%2f53799915%2fcount-number-of-partitions-of-a-set-with-n-elements-into-k-subsets%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