数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 C++ 计算将集合划分成 k 个子集的方法数
给定两个数字 e 和 p。目标是计算将集合的 e 个元素划分成 p 个分区/子集的方法数。
例如
输入
e=4 p=2
输出
Count of number of ways to partition a set into k subsets are: 7
解释
If elements are: a b c d then ways to divide them into 2 partitions are: (a,b,c)−(d), (a,b)−(c,d), (a,b,c)−(d), (a)−(b,c,d), (a,c)−(b,d), (a,c,d)−(b), (a,b,d)−(c). Total 7 ways.
输入
e=2 p=2
输出
Count of number of ways to partition a set into k subsets are: 1
解释
If elements are: a b then ways to divide them into 2 partitions are: (a)− (b). Total 1 way only.
以下程序中使用的算法如下 −
在这个方法中，我们将使用动态规划方法。解决方案中使用的计算始终是递归的。如果我们将元素分成 p 个分区，则 −
如果 e-1 个元素可以分成 p 个分区，方法数为 ways(e-1,p)。那么我们可以将当前元素放入这 p 个分区中的一个，方法数为 p*ways(e-1,p)。
如果 e-1 个元素分成 p-1 个分区，方法数为 ways(e-1,p-1)，那么将 1 个元素放入单独的 1 个分区的方法数为 1*ways(e-1,p-1)。总方法数将为 p*ways(e-1,p)+ways(e-1,p-1)。此方法将变为递归 −
如上所示，将进行重复计算。为了避免这种情况，我们将使用动态规划方法。
将变量、元素和分区作为输入。
函数 partition_k(int elements, int partition) 获取这两个变量并返回将集合划分成 k 个子集的方法数。
使用二维数组 arr[elements + 1][partition + 1] 来存储 ways(e,p) 的值在 arr[e][p] 中。
使用 for 循环从 i=0 到 i=elements，设置 arr[i][0] = 0，因为分区数为 0，则 ways(i,0)=0。
再次使用 for 循环从 j=0 到 i=partitions，设置 arr[0][j] = 0，因为元素数为 0，则 ways(0,i)=0。
现在使用两个 for 循环遍历 arr[][]，从 i=1 到 i<=elements 和 j=1 到 j<=i，并填充其余值。
对于单个元素，ways=1，或者对于将 x 个元素分成 x 个分区，只有一种方法。因此，如果 i==j 或 j==1，则设置 arr[i][j] = 1。
否则，设置 temp_1 = arr[i-1][j-1] 和 temp_2 = arr[i-1][j]，并更新 arr[i][j] = j * temp_2 + temp_1。
在所有循环结束时，我们将有 arr[elements][partition] 作为总方法数。
返回 arr[elements][partition] 作为结果。
示例
#include<iostream>
using namespace std;
int partition_k(int elements, int partition){
int arr[elements + 1][partition + 1];
for(int i = 0; i <= elements; i++){
arr[i][0] = 0;
}
for(int j = 0; j <= partition; j++){
arr[0][partition] = 0;
}
for(int i = 1; i <= elements; i++){
for (int j = 1; j <= i; j++){
if (j == 1 || i == j)
{ arr[i][j] = 1; }
else{
int temp_1 = arr[i−1][j−1];
int temp_2 = arr[i−1][j];
arr[i][j] = j * temp_2 + temp_1;
}
}
}
return arr[elements][partition];
}
int main(){
int elements = 4;
int partition = 2;
cout<<"Count of number of ways to partition a set into k subsets are: "<<partition_k(elements, partition);
return 0;
}输出
如果我们运行上面的代码，它将生成以下输出：
Count of number of ways to partition a set into k subsets are: 7
465 次浏览
