C++でセットをk個のサブセットに分割する方法の数を数えます

例

入力

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要素を方法（e-1、p）でp個のパーティションに分割できる場合。次に、現在の要素をp * way（e-1、p）のこれらのpパーティションの1つに配置できます。

• e-1要素がway（e-1、p-1）でp-1パーティションに分割されている場合、その個別の1パーティションに1つの要素を配置すると、1 * way（e-1、p-1）になります。合計ウェイはp*Ways（e-1、p）+ Ways（e-1、p-1）になります。この方法は再帰的になります-

上に示したように、重複した計算が行われます。これを回避するために、動的プログラミングアプローチを使用します。

• 変数、要素、パーティションを入力として受け取ります。

• 関数partition_k（int要素、intパーティション）は両方の変数を受け取り、セットをk個のサブセットに分割する方法の数を返します。

• 2D配列arr[elements+ 1] [partition + 1]を使用して、way（e、p）の値をarr[e][p]に格納します。

• i=0からi=elementsまでのforループを使用して、パーティションの数が0であるため、arr [i] [0] =0に設定し、way（i、0）=0に設定します。

• 再びj=0からi=partitionへのforループを使用して、要素の数が0であるためarr [0] [j] =0に設定し、way（0、i）=0に設定します。

• ここで、i=1からi<=要素およびj=1からj<=iまでの2つの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