এই সমস্যায়, আমাদের 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 = 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
