部分和問題は、要素が数値の集合 S において、要素の総和が M となる部分集合があるか判定する問題です。たとえば、集合 {2, 3, 5, 8} の場合、総和が 10 となる部分集合は {2, 3, 5} と {2, 8} がありますが、14 となる部分集合はありません。部分集合の総数は、要素数を n とすると 2n 個になるので、n が大きくなるとナイーブな方法では時間がかかってしまいます。実際には、動的計画法などの手法を使うことで、現実的な時間で部分和問題を解くことができます。
最初にナイーブな方法で部分和問題を解いてみましょう。今回は要素を正整数に限定します。部分和問題は「べき集合」を生成する関数 powerSet を作ると簡単です。次のリストを見てください。
リスト : べき集合 powerSet :: [a] -> [[a]] powerSet [] = [[]] powerSet (x:xs) = powerSet xs ++ [x:ys | ys <- powerSet xs]
べき集合を求める関数 powerSet は簡単です。引数が空リストの場合は [ ] を格納したリストを返します。そうでなければ、引数を x:xs で分解します。 そして、powerSet を再帰呼び出しして xs のべき集合を求め、その集合に先頭要素 x を追加します。そして、その集合と xs のべき集合を演算子 ++ で連結します。
簡単な実行例を示します。
ghci> powerSet [2,3,5,8] [[],[8],[5],[5,8],[3],[3,8],[3,5],[3,5,8],[2],[2,8],[2,5],[2,5,8],[2,3],[2,3,8], [2,3,5],[2,3,5,8]]
[2, 3, 5, 8] の部分集合は空集合 [ ] を含めて 16 通りあります。この powerSet を使うと部分和問題のプログラムは次のようになります。
リスト : 部分和問題 subsetSum :: Integer -> [Integer] -> [[Integer]] subsetSum n xs = filter ((==n) . sum) $ powerSet xs
部分集合の総和を sum で求め、n と等しいものを filter で取り出します。それでは実行してみましょう。
ghci> subsetSum 10 [2,3,5,8] [[2,8],[2,3,5]] ghci> subsetSum 14 [2,3,5,8] []
とても簡単ですね。ただし、集合の要素数が多くなると、実行時間がかかるようになります。次のテストプログラムを見てください。
リスト : 簡単なテスト
nums :: [Integer]
nums = [ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946]
test :: Int -> [[Integer]]
test n = subsetSum m xs
where xs = take n nums
m = sum xs - 1
配列 nums はフィボナッチ数列になっています。要素の総和を M とすると、1 から M までの整数は、要素を組み合わせて必ず作ることができます。これはフィボナッチ数列の面白い特徴です。
テストは 総和 - 1 となる組み合わせを subsetSum で求め、その実行時間を計測します。結果は次のようになりました。
ghci> :set +s ghci> test 16 [[2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597]] (0.23 secs, 135,376,688 bytes) ghci> test 17 [[2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584]] (0.54 secs, 284,801,880 bytes) ghci> test 18 [[2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181]] (1.11 secs, 597,805,744 bytes) ghci> test 19 [[2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]] (2.37 secs, 1,252,121,096 bytes) ghci> test 20 [[2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946]] (4.85 secs, 2,617,371,736 bytes) 実行環境 : Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz
要素がひとつ増えると実行時間は約 2 倍になっていることがわかります。要素数を n とすると、subsetSum の実行時間は 2n に比例する遅いプログラムなのです。
次は深さ優先探索に枝刈りを加えた方法で、部分和問題の高速化に挑戦してみましょう。今回の部分和問題は要素を正整数値に限定しているので、二種類の枝刈りを考えることができます。ひとつは部分集合の総和が求める値 N を超えた場合です。残りの要素は正整数なので、これ以上要素を追加しても解を得られないのは明白ですね。もうひとつは、部分集合の総和に残りの要素をすべて足しても N に満たない場合です。これも解を得られないのは明白です。
部分集合の総和を S, 残りの要素の総和を R, 求める値を N とすると、探索を行う条件は次の式で表すことができます。
S < N && S + R >= N
これをプログラムすると次のようになります。
リスト : 部分和問題 (dfs + cut)
subsetSum1 :: Integer -> [Integer] -> [[Integer]]
subsetSum1 n xs = iter [] 0 xs (sum xs) []
where iter a m [] _ b
| n == m = a : b
| otherwise = b
iter a m (y:ys) r b
| n == m = a : b
| m < n && m + r >= n =
iter a m ys (r - y) $ iter (y:a) (m + y) ys (r - y) b
| otherwise = b
実際の処理は局所関数 iter で行います。引数 m は求めている部分集合の総和、r は残りの要素の総和を表します。引数 b は結果を格納する累積変数です。m < n かつ m + r >= n ならば条件を満たすので、iter を再帰呼び出しして探索を続行します。とても簡単ですね。
それでは試してみましょう。
リスト : テストプログラム
test1 :: Int -> [[Integer]]
test1 n = subsetSum1 m xs
where xs = take n nums
m = sum xs - 1
ghci> test1 16 [[1597,987,610,377,233,144,89,55,34,21,13,8,5,3,2]] (0.00 secs, 145,184 bytes) ghci> test1 17 [[2584,1597,987,610,377,233,144,89,55,34,21,13,8,5,3,2]] (0.00 secs, 151,456 bytes) ghci> test1 18 [[4181,2584,1597,987,610,377,233,144,89,55,34,21,13,8,5,3,2]] (0.00 secs, 157,728 bytes) ghci> test1 19 [[6765,4181,2584,1597,987,610,377,233,144,89,55,34,21,13,8,5,3,2]] (0.00 secs, 164,000 bytes) ghci> test1 20 [[10946,6765,4181,2584,1597,987,610,377,233,144,89,55,34,21,13,8,5,3,2]] (0.00 secs, 171,032 bytes)
とても速くなりましたね。ただし、これは枝刈りがうまくいった場合であり、データによっては枝刈りが機能しない場合もありえます。たとえば、xs の最後尾の要素から 1 を引いた値を判定してみましょう。結果は次のようになりました。
リスト : テストプログラム
test1' :: Int -> [[Integer]]
test1' n = subsetSum1 m xs
where xs = take n nums
m = last xs - 1
ghci> test1' 16 [[987,377,144,55,21,8,3,1]] (0.11 secs, 51,644,424 bytes) ghci> test1' 17 [[1597,610,233,89,34,13,5,2]] (0.21 secs, 103,200,720 bytes) ghci> test1' 18 [[2584,987,377,144,55,21,8,3,1]] (0.40 secs, 206,313,344 bytes) ghci> test1' 19 [[4181,1597,610,233,89,34,13,5,2]] (0.79 secs, 412,534,600 bytes) ghci> test1' 20 [[6765,2584,987,377,144,55,21,8,3,1]] (1.58 secs, 824,977,144 bytes)
実行時間はそれほど速くなりません。実をいうと、データの並び方によって実行時間は大きく左右されます。興味のある方はいろいろ試してみてください。
今度は前回説明した「動的計画法」で部分和問題を解いてみましょう。部分和問題の場合、総和が N となる部分集合があるか判定するだけでよければ、動的計画法で解くことが可能です。
部分和問題の場合、要素をひとつずつ追加しながら、総和 N となる部分集合があるか判定します。簡単な例を示しましょう。次の図を見てください。
xs = {2, 3, 5, 8}, N = 10
０ １ ２ ３ ４ ５ ６ ７ ８ ９ 10
-------------------------------------------------
0: {} ○ × × × × × × × × × ×
1: {2} ○ × ○ × × × × × × × ×
2: {2, 3} ○ × ○ ○ × ○ × × × × ×
3: {2, 3, 5} ○ × ○ ○ × ○ × ○ ○ × ○
4: {2, 3, 5, 8} ○ × ○ ○ × ○ × ○ ○ × ○
上図は xs = {2, 3, 5, 8} で N = 10 の部分集合があるか判定する場合です。最初に N + 1 の配列 Ai を用意します。空集合の総和は 0 なので A0[0] に○をセットします。次に、要素 2 を追加します。部分集合は { } と {2} になります。A1[0] と A1[2] に○をセットします。その次に要素 3 を追加します。追加される部分集合は {3} と {2, 3} になるので、A2[0], A2[2], A2[3] と A2[5] に○をセットします。
つまり、i 番目の要素 x を追加する場合、Ai-1 で○が付いている位置を y とすると、Ai[y] と Ai[x + y] に○をセットすればいいわけです。添字 y は部分集合の総和を表しています。Ai[y] に○をセットすることは、その部分集合に x を加えないことを意味し、Ai[x + y] に○をセットすることは、その部分集合に x を追加することを意味するわけです。
次に 5 を追加します。A2 の○の位置は 0, 2, 3, 5 なので、これに 5 を足した 5, 7, 8, 10 の位置に○をセットします。最後に 8 を追加します。A3 の○の位置は 0, 2, 3, 5, 7, 8, 10 なので、これに 8 を足した 8, 10 の位置に○をセットします。A4[10] の値が○になので、部分和が 10 となる部分集合があることがわかります。
もうひとつ簡単な例を示しましょう。今度は総和が 14 となる部分集合があるか判定します。
xs = {2,3,5,8}, N = 14
０ １ ２ ３ ４ ５ ６ ７ ８ ９ 10 11 12 13 14
----------------------------------------------------------
0: {} ○ × × × × × × × × × × × × × ×
1: {2} ○ × ○ × × × × × × × × × × × ×
2: {2,3} ○ × ○ ○ × ○ × × × × × × × × ×
3: {2,3,5} ○ × ○ ○ × ○ × ○ ○ × ○ × × × ×
4: {2,3,5,8} ○ × ○ ○ × ○ × ○ ○ × ○ ○ × ○ ×
3 番目で○の位置は 0, 2, 3, 5, 7, 8, 10 です。次は 8 を追加しますが、総和 14 より大きい値は不要なので、8, 10, 11, 13 の位置に○を追加します。14 の位置は×なので、総和が 14 となる部分集合は無いことがわかります。
プログラムは次のようになります。
リスト : 部分和問題 (動的計画法)
subsetSum2 :: Integer -> [Integer] -> IO Bool
subsetSum2 n xs = do
a <- newArray (0, n) False :: IO (IOArray Integer Bool)
writeArray a 0 True
mapM_ (\x -> mapM_ (\y -> do f <- readArray a y
when f $ do writeArray a (x + y) True)
[n - x, n - x - 1 .. 0])
xs
readArray a n
○を True で、×を False で表します。配列をひとつで済ますため、配列の後ろから True の位置を検索していることに注意してください。また、検索の開始位置を n - x とすることで、True をセットするときの範囲チェックを省略しています。今回のプログラムでは xs の要素をすべてチェックしていますが、x + y が n と等しくなったら True を返えすようにプログラムしてもかまいません。あとは特に難しいところはないと思います。
それでは実際に試してみましょう。テストプログラムを示します。
リスト : テストプログラム
test2 :: Int -> IO Bool
test2 n = subsetSum2 m xs
where xs = take n nums
m = sum xs - 1
実行結果は次のようになりました。
ghci> test2 16 True (0.07 secs, 69,518,080 bytes) ghci> test2 17 True (0.11 secs, 119,491,352 bytes) ghci> test2 18 True (0.19 secs, 204,699,784 bytes) ghci> test2 19 True (0.51 secs, 349,606,816 bytes) ghci> test2 20 True (0.88 secs, 595,456,440 bytes)
ナイーブな方法よりも高速になりましたが、dfs + cut にはかないませんでした。集合の要素数を M, 総和を N とすると、今回のプログラムの実行速度は N * M に比例します。たとえば、N の値を 最後尾の要素 - 1 とすると、実行結果は次のようになります。
リスト : テストプログラム
test2' :: Int -> IO Bool
test2' n = subsetSum2 m xs
where xs = take n nums
m = last xs - 1
ghci> test2' 16 True (0.03 secs, 24,306,040 bytes) ghci> test2' 17 True (0.04 secs, 41,969,376 bytes) ghci> test2' 18 True (0.07 secs, 72,210,160 bytes) ghci> test2' 19 True (0.12 secs, 123,828,136 bytes) ghci> test2' 20 True (0.19 secs, 211,696,040 bytes)
N が小さくなったので、実行時間も速くなりました。このように、動的計画法では N が大きくなると、どうしても時間がかかるようになります。そこで、配列を使わずにプログラムを作ってみましょう。
配列を使う場合、N が大きくなると True を検索する処理に時間がかかるようになります。そこで、配列の代わりにモジュール Data.Set を使って部分集合の総和を管理することにします。プログラムは次のようになります。
リスト : 部分和問題
import qualified Data.Set as S
subsetSum3 :: Integer -> [Integer] -> Bool
subsetSum3 n xs = iter xs (S.singleton 0)
where iter [] s = S.member n s
iter (x:xs) s = iter xs $ foldl (\s' y -> if x + y <= n
then S.insert (x + y) s'
else s')
s
(S.elems s)
実際の処理は局所関数 iter で行います。最初に部分集合の総和を管理するセット s を 0 に初期化します。関数 S.elems で集合の要素を求め、それを foldl に渡します。ラムダ式の中で、リストの要素 x と集合の要素 y を足し算し、それが n 以下であれば S.insert で集合に追加します。最後に、S.member で集合 s に n が含まれているかチェックします。
それでは実行結果を示します。
リスト : テストプログラム
test3 :: Int -> Bool
test3 n = subsetSum3 m xs
where xs = take n nums
m = sum xs - 1
test3' :: Int -> Bool
test3' n = subsetSum3 m xs
where xs = take n nums
m = last xs - 1
ghci> test3 16 True (0.01 secs, 6,504,032 bytes) ghci> test3 17 True (0.01 secs, 10,852,488 bytes) ghci> test3 18 True (0.02 secs, 18,253,008 bytes) ghci> test3 19 True (0.04 secs, 30,656,808 bytes) ghci> test3 20 True (0.06 secs, 51,479,704 bytes)
ghci> test3' 16 True (0.01 secs, 3,357,144 bytes) ghci> test3' 17 True (0.01 secs, 5,573,656 bytes) ghci> test3' 18 True (0.02 secs, 9,312,352 bytes) ghci> test3' 19 True (0.02 secs, 15,547,568 bytes) ghci> test3' 20 True (0.04 secs, 25,955,520 bytes)
subsetSum2 よりも高速になりました。ちなみに、dfs + cut と同様の枝刈りを入れると、実行速度はもう少し速くなります。興味のある方は試してみてください。