前回の（その６）では色々な分割数の問題を解く関数をnumpyのconvolveを使って実装しました。今回は重複組合せを解く関数を作ります。
両替問題を解く（個数制限あり）
（その５）で作ったコードのデータに 最低使う個数 を加えて１つのコインを (w, m0, m1) で表します
- w: 重み=コインの価値
- m0: 最低使う個数
- m1: 最大個数（制限なしは0）
例えば 5pのコインは最低1個 最大10個使うならデータは(5,1,10) となります。
例題１ 1p,2p,5p,10pのコインを使って20pにするのは何通りあるか求めよ。ただし1p,2p,5pは最低１個で最大5個までしか使えない
この時のデータは以下の様になります。これを関数 polに与えて多項式の係数を作ります。
def pol(pd, N):
w, m0, m1 = pd
return [1 if (i % w == 0) and (i >= m0*w) else 0 for i in range((N if m1==0 else min(N, m1*w))+1)]
N, pdata = 20, [(1,1,5),(2,1,5),(5,1,5),(10,0,0)]
for pd in pdata:
print(pd, pol(pd, N))
# (1, 1, 5) [0, 1, 1, 1, 1, 1]
# (2, 1, 5) [0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
# (5, 1, 5) [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]
# (10, 0, 0) [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
重複組合せ（制限あり）の場合
典型的な重複組合せの問題を考えます。
例題２ 赤の玉が1つ，青の玉が2つ，黄の玉が2つある。この中から4つ玉を選ぶときに得られる色のパターンが何通りあるか求めよ
この場合は色の違う1pコインと考えればよいので
N, pdata = 4, [(1,0,1),(1,0,2),(1,0,2)]
# (1, 0, 1) [1, 1]
# (1, 0, 2) [1, 1, 1]
# (1, 0, 2) [1, 1, 1]
重複組合せ（制限なし）の場合
例題3 青，赤，黒の三種類の玉がたくさんある。この中から4つ玉を選ぶときに得られる色のパターンが何通りあるか求めよ。
N, pdata = 4, [(1,0,0),(1,0,0),(1,0,0)]
となりますが、同じ値の繰り返しになるので、これを以下のように表現します。
N, pdata = 4, [(1,0,0),('*', 3)] # repeat (1,0,0) 3 times
データから解を求める関数 polmult
データからnp.convolveを使って解を求める関数 polmultです。リピート記号"*"がある場合にジェネレーターを変更してます。
import numpy as np
from functools import reduce
def polmult(pdata, N):
if pdata[-1][0] == '*':
gen = (pol(pdata[0], N) for _ in range(pdata[-1][1])) # repeat pdata[-1][1] times
else:
gen = (pol(pd, N) for pd in pdata)
return reduce(lambda x, y: np.convolve(x,y)[:N+1], gen, [1])
例題1-3の解答
あとはデータをpolmultに与えればOKです。polmultのリターンは多項式の係数全部なのでN番目の要素を取り出せば答えになります。
title, N, pdata = "例題１", 20, [(1,1,5),(2,1,5),(5,1,5),(10,0,0)]
print(f"# {title}の答え: {polmult(pdata, N)[N]}")
# # 例題１の答え: 7
title, N, pdata = "例題２", 4, [(1,0,1),(1,0,2),(1,0,2)]
print(f"# {title}の答え: {polmult(pdata, N)[N]}")
# 例題２の答え: 3
title, N, pdata = "例題３", 4, [(1,0,0),('*', 3)] # repeat (1,0,0) 3 times
print(f"# {title}の答え: {polmult(pdata, N)[N]}")
# 例題３の答え: 15
応用例
例題４ コインを10回投げたときに表が0-10回出る場合の数
すなわち二項係数です。多項式の係数をそのままプリント
title, N, pdata = "例題４", 10, [(1,0,1),('*', 10)]
print(f"# {title}の答え: {polmult(pdata, N)}")
# 例題４の答え: [ 1 10 45 120 210 252 210 120 45 10 1]
例題５ サイコロを３回投げたときに目の和が10になる場合の数
サイコロは０がないので最小値=1、最大値=6とします
title, N, pdata = "例題５", 10, [(1,1,6),('*', 3)]
print(f"# {title}の答え: {polmult(pdata, N)[N]}")
# 例題５の答え: 27
例題６ x+y+z = 10を満たす、負でない整数 (x,y,z) の組は何通り？
これは例題3と同じですね。
title, N, pdata = "例題６", 10, [(1,0,0),('*', 3)]
print(f"# {title}の答え: {polmult(pdata, N)[N]}")
# 例題６の答え: 66
例題7 x+y+z <= 10を満たす、負でない整数 (x,y,z)の組は何通り？
これは polmultが1-10の係数を返すことを利用すればデータは例題６と同じでsumを取ればいいです
print(f"# {title}の答え: {sum(polmult(pdata, N))}")
# 例題７の答え: 286
例題８(x+y+z+p+q)**4を展開して同類項をまとめたとき異なる項は何通りありますか
５文字から４個を選ぶ重複組合せなので
N, K = 4, 5
title, pdata = "例題８", [(1,0,0), ("*", K)]
print(f"# {title}の答え: {polmult(pdata, N)[N]}")
# 例題８の答え: 70
例題９ 【分割数】10を自然数の和で何通りの組み合わせで表せるか？
両替問題に置き換えて1p-10pを組み合わせて10pにすると考えます。分割数に関しては（その６）で他の例も取り上げています。
title, N, pdata = "例題９", 10, [(i,0,0) for i in range(1,10+1)]
print(f"# {title}の答え: {polmult(pdata, N)[N]}")
# 例題９の答え: 42
この考え方はProject Euler, Problem 881: Divisor Graph Widthを解くのに役に立ちます。
（開発環境：Google Colab）