ผลรวมของความต่างของทุก Subset ใน C++

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

สูตรคือ

sumSubsetDifference = Σ [last(s) - first(s)] โดยที่ s คือ subset ของเซต S

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต −

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

เอาต์พุต −

คำอธิบาย − ทุก subset คือ −

{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

วิธีง่ายคือหาความต่างระหว่าง last และ first สำหรับทุก subset แล้วรวมกัน แต่นี้ไม่ใช่วิธีที่มีประสิทธิภาพที่สุด

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

ดังนั้น

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

สำหรับเซต S ที่มีองค์ประกอบ {s1, s2, s3, ... sn}

Subset ที่เริ่มด้วย s1 สร้างได้จากการจัดหมู่ขององค์ประกอบกับ {s2, s3, ... sn} ซึ่งให้ 2^(n-1) เซต

เช่นเดียวกัน subset ที่เริ่มด้วย s2 ให้ 2^(n-2) เซต

สรุปได้ว่า subset ที่เริ่มด้วย si ให้ 2^(n-i) เซต

ดังนั้น ผลรวมขององค์ประกอบแรกของทุก subset คือ −

SumFirst = a1·2^(n-1) + a2·2^(n-2) + a3·2^(n-3) + ... + an·2^(n-n)

เช่นเดียวกัน เราจะคำนวณ SumLast โดยการ固定องค์ประกอบสุดท้าย

SumLast = a1·2^(n-n) + a2·2^(n-(n-1)) + a3·2^(n-(n-2)) + ... + an·2^(n-(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