C++ですべての部分集合の積の総和を求めるアルゴリズムと効率的な解法

この問題では、N個の数値からなる配列 arr[] が与えられ、考えられるすべての部分集合について要素の積を計算し、その総和を求めるプログラムをC++で作成します。

基本的な考え方は、まずすべての部分集合を列挙し、それぞれの部分集合に含まれる要素の積を求め、最後にそれらをすべて加算するというものです。

問題例

入力:

arr[] = {4, 5, 6}

出力:

209

説明:

arr[] のすべての部分集合: {4}, {5}, {6}, {4, 5}, {5, 6}, {4, 6}, {4, 5, 6}
積の総和
= (4) + (5) + (6) + (4×5) + (5×6) + (4×6) + (4×5×6)
= (4) + (5) + (6) + (20) + (30) + (24) + (120)
= 209

解法1: ビット全列挙による素朴なアプローチ

最もシンプルな解法は、集合のすべての部分集合を生成し、各部分集合の要素の積を計算して合計に加える方法です。ビット演算を利用すると、カウンター値の各ビットが立っているかどうかで、対応する要素を部分集合に含めるかどうかを判定できます。

実装例

#include<iostream>
#include<math.h>
using namespace std;

int findSumProductSubset(int *arr, int set_length) {
    unsigned int size = pow(2, set_length); // 部分集合の総数は 2^n
    int sum = 0;
    int product;
    for(int counter = 1; counter < size; counter++) {
        product = 1;
        for(int j = 0; j < set_length; j++) {
            // counter の j ビット目が 1 なら arr[j] を部分集合に含める
            if(counter & (1<<j))
                product *= arr[j];
        }
        sum += product;
    }
    return sum;
}

int main() {
    int arr[] = {4, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"すべての部分集合の積の総和は "<<findSumProductSubset(arr, n);
}

出力結果

すべての部分集合の積の総和は 209

このアプローチはすべての部分集合を生成するため、時間計算量は O(2ⁿ) と指数関数的になり、要素数が増えると急激に遅くなります。そこで、より効率的な解法として、解に潜む数学的なパターンを利用する方法を考えます。

解法2: 数学的パターンを利用した効率的なアプローチ

ここで、3つの数 x, y, z からなる集合を例に考えてみましょう。求めるべき総和は次の通りです。

sum = x + y + z + xy + yz + xz + xyz

この式を因数分解の要領で変形していきます。

sum = x + xz + y + yz + xy + xyz + z + 1 − 1
sum = x(1+z) + y(1+z) + xy(1+z) + 1(z+1) − 1
sum = (x + y + xy + 1)(1+z) − 1
sum = (x(1+y) + 1(1+y))(1+z) − 1
sum = (1 + x)(1 + y)(1 + z) − 1

この規則性は一般化でき、n 個の要素 e1, e2, …, en からなる集合については次の公式が成り立ちます。

sum = (1 + e1) × (1 + e2) × … × (1 + en) − 1

つまり、各要素に 1 を加えた値をすべて掛け合わせ、最後に 1 を引くだけで答えが求まります。配列を一度走査するだけなので、時間計算量は O(n) と非常に効率的です。

実装例

#include <iostream>
using namespace std;

int productOfSubsetSums(int arr[], int n) {
    int sum = 1;
    for (int i = 0; i < n; ++i)
        sum *= (arr[i] + 1); // 各要素に 1 を加えて順に掛ける
    sum--; // 最後に 1 を引く
    return sum;
}

int main() {
    int arr[] = {5, 6, 8, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"すべての部分集合の積の総和は "<<productOfSubsetSums(arr, n);
    return 0;
}

出力結果

すべての部分集合の積の総和は 3779

まとめ

すべての部分集合を列挙する方法では O(2ⁿ) の計算量が必要ですが、「(各要素 + 1) の総乗 − 1」という公式を使えば O(n) で答えを求められます。なお、要素の値や個数が大きい場合は積がオーバーフローする可能性があるため、必要に応じて long long 型などの使用を検討してください。