주어진 두 개의 숫자 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개의 파티션으로 나눌 수 있는 경우(e-1,p). 그런 다음 현재 요소를 p*ways(e-1,p)의 이러한 p 파티션 중 하나에 넣을 수 있습니다.
-
e−1 요소가 way(e−1,p−1)로 p−1 파티션으로 분할되면 별도의 1 파티션에 1개의 요소를 넣으면 1*ways(e−1,p−1)가 됩니다. 총 경로는 bep*ways(e−1,p)+ways(e−1,p−1)입니다. 이 메서드는 재귀적입니다 -
위와 같이 중복 계산이 수행됩니다. 이를 피하기 위해 동적 프로그래밍 접근 방식을 사용합니다.
-
변수, 요소 및 파티션을 입력으로 사용합니다.
-
partition_k(int elements, int partition) 함수는 두 변수를 모두 취하여 세트를 k 하위 집합으로 분할하는 방법의 수를 반환합니다.
-
2D 배열 arr[elements + 1][partition + 1]을 사용하여 way(e,p)의 값을 arr[e][p]에 저장합니다.
-
i=0에서 i=elements까지 for 루프를 사용하여 파티션 수가 0이고 way(i,0)=0이므로 arr[i][0] =0을 설정합니다.
-
다시 j=0에서 i=partitions까지 for 루프를 사용하여 요소 수가 0이고 way(0,i)=0이므로 arr[0][j] =0을 설정합니다.
-
이제 i=1에서 i<=elements 및 j=1에서 j<=i까지 두 개의 for 루프를 사용하여 arr[][]을 순회합니다. 나머지 값을 채웁니다.
-
단일 요소의 경우 way=1 또는 x 요소를 x 파티션으로 나누는 경우에는 1가지 방법만 있습니다. 따라서 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