C++で可能なすべてのサブセットの積の合計

この問題では、N個の数の配列arr[]が与えられます。私たちの仕事は、考えられるすべてのサブセットの積の合計を見つけるプログラムを作成することです。

ここでは、すべてのサブセットを検索してから、各サブセットのすべての要素の積を検索します。次に、すべての値を加算して合計を計算します。

問題を理解するために例を見てみましょう

入力

arr[] = {4, 5, 6}

出力

209

説明-

All subsets of arr[] are: {4}, {5}, {6}, {4, 5}, {5, 6}, {4, 6}, {4, 5, 6}
Sum of product
= (4) + (5) + (6) + (4*5) + (5*6) + (4*6) + (4*5*6)
= (4) + (5) + (6) + (20) + (30) + (24) + (120)
= 209

問題を解決するための簡単なアプローチは、セットのすべてのサブセットを見つけて、各セットの要素の積を計算することです。そして、すべての製品を追加し、すべてのサブセットがトラバースされた後、すべての最終合計を返します。

例

ソリューションの動作を説明するプログラム

#include<iostream>
#include<math.h>
using namespace std;
int findSumProductSubset(int *arr, int set_length) {
   unsigned int size = pow(2, set_length);
   int sum = 0;
   int product;
   for(int counter = 1; counter < size; counter++) {
      product = 1;
      for(int j = 0; j < size; j++) {
         if(counter & (1<<j))
         product *= arr[j];
      }
      sum += product;
   }
   return sum;
}
int main() {
   int arr[] = {4, 5, 6};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The sum of the product of all subsets is "<<findSumProductSubset(arr, n);
}

出力

The sum of the product of all subsets is 209

上記のアプローチでは、すべてのサブセットが生成されるため、時間計算量が指数関数的に複雑になります。したがって、これは最も効率的なアプローチではありません。

より効率的なアプローチは、ソリューションのパターンを見つけることです。

それでは、x、y、zの3つの数字のセットを見てみましょう。

合計=x+ y + z + xy + yz + xz + xyz

合計=x+ xz + y + yz + xy + xyz + z + 1-1

合計=x（1 + z）+ y（1 + z）+ xy（1 + z）+ 1（z + 1）-1

合計=（x + y + xy + 1）（1 + z）-1

合計=（x（1 + y）+ 1（1 + y））（1 + z）-1

合計=（1 + x）*（1 + y）*（1 + z）-1

これは、次の方法で一般化できます。

n要素セットの場合

sum =（1+ e1）*（1 + e2）*…*（1 + en）-1

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int productOfSubsetSums(int arr[], int n) {
   int sum = 1;
   for (int i = 0; i < n; ++i )
   sum *= (arr[i] + 1);
   sum --;
   return sum;
}
int main() {
   int arr[] = {5, 6, 8 , 9};
   int n = sizeof(arr)/sizeof arr[0];
   cout<<"Sum of product of all possible subsets is "<<productOfSubsetSums(arr, n);
   return 0;
}

出力

Sum of product of all possible subsets is 3779