C++で部分集合の差の合計を求める効率的なアルゴリズム

問題の概要

この問題では、n個の数からなる集合Sが与えられ、各部分集合sについて「最後の要素と最初の要素の差」を計算し、その総和を求めるプログラムを作成します。

数式で表すと次のようになります。

sumSubsetDifference = Σ [last(s) − first(s)]
※ sは集合Sの部分集合

入出力例で理解しよう

入力 −

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

出力 − 24

説明 − すべての部分集合とその差は以下の通りです。

{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
合計 = 1 + 8 + 7 + 8 = 24

素朴な解法とその課題

最もシンプルな方法は、すべての部分集合を列挙し、それぞれの「最後の要素 − 最初の要素」を計算して合計するものです。しかし、部分集合の数は2ⁿ個に増加するため、要素数が大きくなると現実的な時間内で処理できません。そこで、数学的な性質を利用した効率的な解法を紹介します。

効率的な解法の考え方

各要素が「先頭要素」として何回登場するか、「末尾要素」として何回登場するかを数えれば、部分集合を実際に生成しなくても合計を求められます。

sumSetDifference(S) = Σlast(s) − Σfirst(s)

集合Sの要素が {a1, a2, a3, …, an}（昇順ソート済み）である場合を考えます。

• a1を先頭に含む部分集合は、残りの要素 {a2, a3, …, an} の任意の組み合わせで作れるため、2ⁿ⁻¹ 個
• a2を先頭に含む部分集合は 2ⁿ⁻² 個
• 一般化すると、aiを先頭に含む部分集合は 2ⁿ⁻ⁱ 個

したがって、全部分集合の先頭要素の合計は次の式になります。

SumFirst = a1·2n−1 + a2·2n−2 + a3·2n−3 + … + an·20

同様に末尾要素に着目すると、anが末尾になる部分集合は2ⁿ⁻¹個、a1が末尾になるのは1個なので、次の式が得られます。

SumLast = a1·20 + a2·21 + a3·22 + … + an·2n−1

求める答えは SumLast − SumFirst です。

C++での実装例

上記の解法を実装したプログラムが以下です。

#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

コードのポイント

• CalcSumFirst: 各要素に「先頭要素として登場する回数」2ⁿ⁻ⁱ⁻¹ を掛けて合計します。
• CalcSumLast: 各要素に「末尾要素として登場する回数」2ⁱ を掛けて合計します。

このアルゴリズムの時間計算量はO(n)、空間計算量はO(1)です。全部分集合を列挙するO(2ⁿ)の素朴な手法と比べて劇的に高速化できるのが大きな利点です。なお、この手法は集合が昇順にソートされていることが前提となるため、入力が未ソートの場合は事前にsort()などで並べ替えておきましょう。