इस समस्या में, हमें 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 समस्या का एक सरल समाधान यह है कि सभी उपसमुच्चयों के लिए अंतिम और पहले के बीच का अंतर ज्ञात किया जाए और फिर उन्हें योग आउटपुट प्राप्त करने के लिए जोड़ा जाए। यह सबसे प्रभावी समाधान नहीं है, इसलिए आइए अधिक कुशल समाधान पर चर्चा करें।
एन तत्वों के एक सेट एस के लिए, सरणी के एक तत्व से शुरू होने वाले सभी सबसेट की संख्या का उपयोग करके योग की गणना भी की जा सकती है। और परिणाम खोजने के लिए इसे सारांशित करें।
तो,
sumSetDifference(S) = Σ [last(s) - Σfirst(s)]
तो, तत्वों के साथ एक सेट एस के लिए {s1, s2, s3, … sn}।
s1 से शुरू होने वाला सबसेट {s2, s3, … sn} वाले तत्वों के संयोजन का उपयोग करके बनाया जा सकता है। यह 2 n-1 . देगा सेट।
इसी तरह s2 से शुरू होने वाले सबसेट के लिए 2 n-2 . देता है सेट।
इसे सामान्य करते हुए, Si से शुरू होने वाला सबसेट 2 n-i . दिया गया है ।
तो, सभी सबसेट के पहले तत्व का योग है -
SumFirst = a1.2n-1 + a2.2n-2 + a3.2n-3 + … + an.2n-n
इसी तरह, हम अंतिम तत्व को ठीक करते हुए योग की गणना करेंगे।
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