Pythonで配列のすべての部分集合から得られる最大差の合計を効率的に求める方法

問題の概要

要素が重複してもよい n 個の値を持つ配列 A が与えられたとします。このとき、与えられた配列から作れるすべての部分集合について、その部分集合内の最大値と最小値の差（max(s) − min(s)）を求め、それらの合計を計算するのが目的です。

ここで、max(s) は部分集合 s 内の最大値、min(s) は最小値を表します。要素が1つだけの部分集合では最大値と最小値が一致するため、差は 0 になります。

具体例

入力が A = [1, 3, 4] の場合を考えてみましょう。

• [1]、[3]、[4] → 差はそれぞれ 0
• [1, 3] → 3 − 1 = 2
• [1, 4] → 4 − 1 = 3
• [3, 4] → 4 − 3 = 1
• [1, 3, 4] → 4 − 1 = 3

これらを合計すると 0 + 0 + 0 + 2 + 3 + 1 + 3 = 9 となり、出力は 9 になります。

解法のアプローチ

全部分集合を実際に列挙すると計算量が爆発するため、各要素の「寄与」に着目した効率的な方法を使います。

考え方のポイント

配列を昇順にソートした後、インデックス i の要素 A[i] に注目すると：

• A[i] が最大値として現れる回数は 2ⁱ 回（自分より小さい要素だけで構成される部分集合に自分を加える組み合わせ）
• A[i] が最小値として現れる回数は 2ⁿ⁻¹⁻ⁱ 回

したがって、答えは次の式で表せます。

答え = Σ A[i] × (2^i − 2^(n−1−i))

大きな指数でもオーバーフローしないよう、剰余 N = 1000000007 を取りながらホーナー法の要領で累積計算していきます。

アルゴリズムの手順

1. n を配列 A のサイズとする
2. 配列 A を昇順にソートする
3. sum_min = 0、sum_max = 0 で初期化する
4. i を 0 から n−1 まで繰り返し：
   • sum_max = 2 × sum_max + A[n−1−i] を計算し、N で剰余を取る
   • sum_min = 2 × sum_min + A[i] を計算し、N で剰余を取る
5. (sum_max − sum_min + N) mod N を返す

実装例

以下は Python による実装です。

N = 1000000007

def get_max_min_diff(A):
    n = len(A)
    A.sort()
    sum_min = 0
    sum_max = 0
    for i in range(n):
        sum_max = 2 * sum_max + A[n - 1 - i]
        sum_max %= N
        sum_min = 2 * sum_min + A[i]
        sum_min %= N
    return (sum_max - sum_min + N) % N

A = [1, 3, 4]
print(get_max_min_diff(A))

入力

[1, 3, 4]

出力

9

計算量について

この手法では、ソートに O(n log n)、集計ループに O(n) しかかかりません。全部分集合を列挙する O(2ⁿ) の方法と比べ、非常に高速に処理できるのが大きな利点です。