ผลรวมของความแตกต่างของเซตย่อยใน C++

ในปัญหานี้ เราได้รับชุด S ของจำนวน n งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมของความแตกต่างของเซตย่อย ซึ่งเป็นความแตกต่างขององค์ประกอบสุดท้ายและองค์ประกอบแรกของเซ็ตย่อย

สูตรคือ

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

วิธีแก้ปัญหาอย่างง่ายคือค้นหาความแตกต่างระหว่างชุดย่อยสุดท้ายและชุดแรกสำหรับชุดย่อยทั้งหมด แล้วเพิ่มเพื่อให้ได้ผลลัพธ์รวม นี่ไม่ใช่วิธีแก้ปัญหาที่มีประสิทธิภาพมากที่สุด เรามาคุยกันถึงวิธีแก้ปัญหาที่มีประสิทธิภาพมากกว่านี้กันเถอะ

สำหรับชุด S ขององค์ประกอบ n รายการ สามารถคำนวณผลรวมโดยใช้จำนวนของชุดย่อยทั้งหมดที่เริ่มต้นจากองค์ประกอบของอาร์เรย์ และผลรวมเพื่อหาผลลัพธ์

ดังนั้น

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

ดังนั้น สำหรับเซต 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 แก้ไของค์ประกอบสุดท้าย

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