এই সমস্যাতে, আমাদের n সংখ্যক এলিমেন্টের একটি সেট S দেওয়া আছে। আমাদের কাজ হলো সাবসেট পার্থক্যের যোগফল বের করার প্রোগ্রাম লিখা, যেটি সাবসেটের শেষ এবং প্রথম এলিমেন্টের পার্থক্য।
ফর্মুলা হচ্ছে,
sumSubsetDifference = Σ [last(s) - first(s)] s হলো সেট 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)]
একটি সেট S যার এলিমেন্টগুলো {s1, s2, s3, … sn}।
s1 দিয়ে শুরু হওয়া সাবসেটগুলো {s2, s3, … sn} এলিমেন্টগুলোর কোম্বিনেশন দিয়ে তৈরি হবে। এতে 2n-1টি সেট বने।
এভাবে s2 দিয়ে শুরু হওয়া সাবসেট 2n-2টি।
সাধারণ করলে, Si দিয়ে শুরু হওয়া সাবসেট 2n-i।
তাহলে সব সাবসেটের প্রথম এলিমেন্টের যোগফল −
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
