C++でのサブセットの違いの合計

この問題では、n個の集合Sが与えられます。私たちのタスクは、サブセットの最後の要素と最初の要素の差であるサブセットの差の合計を見つけるプログラムを作成することです。

式は、

sumSubsetDifference = Σ [last(s) - first(s)]
s are subsets of the set S.

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

入力 −

S = {1, 2, 9} n = 3

出力 −

説明 −すべてのサブセットは−

{1}, last(s) - first(s) = 0
{2}, last(s) - first(s) = 0
{9}, last(s) - first(s) = 0
{1, 2}, last(s) - first(s) = 1
{1, 9}, last(s) - first(s) = 8
{2, 9}, last(s) - first(s) = 7
{1, 2, 9}, last(s) - first(s) = 8
Sum = 1 + 8 + 7 + 8 = 24

この問題の簡単な解決策は、すべてのサブセットの最後と最初の違いを見つけ、それらを追加して合計出力を取得することです。これは最も効果的な解決策ではないので、より効率的な解決策について話し合いましょう。

n個の要素のセットSの場合、配列の要素から始まるすべてのサブセットの数を使用して合計を計算することもできます。そして、それを合計して結果を見つけます。

だから、

sumSetDifference(S) = Σ [last(s) - Σfirst(s)]

したがって、要素が{s1、s2、s3、…sn}の集合Sの場合。

s1で始まるサブセットは、要素と{s2、s3、…sn}の組み合わせを使用して作成できます。これにより、2 ^n-1 が得られます セット。

同様に、s2で始まるサブセットの場合、2 ^n-2 が得られます。 セット。

一般化すると、2 ^n-i が与えられたSiで始まるサブセット 。

したがって、すべてのサブセットの最初の要素の合計は-

SumFirst = a1.2n-1 + a2.2n-2 + a3.2n-3 + … + an.2n-n

同様に、最後の要素を修正するsumLastを計算します。

SumLast = a1.2n-n + a1.2n - (n-1) + a3.2n - (n-2) + ... + an.2n - (n-(n-1))

例

上記の解決策を説明するプログラム

#include<iostream>
#include<math.h>
using namespace std;
int CalcSumFirst(int S[], int n) {
   int sum = 0;
   for (int i = 0; i < n; i++)
      sum = sum + (S[i] * pow(2, n-i-1));
   return sum;
}
int CalcSumLast(int S[], int n) {
   int sum = 0;
   for (int i = 0; i < n; i++)
      sum = sum + (S[i] * pow(2, i));
   return sum;
}
int main() {
   int S[] = {1, 4, 9, 6};
   int n = 4;
   int sumSetDiff = CalcSumLast(S, n) - CalcSumFirst(S, n);
   printf("The sum of subset differences is %d", sumSetDiff);
   return 0;
}

出力

The sum of subset differences is 45