n個の要素をk個にグループ分けする組み合わせの問題は、全てn個の玉をk個の箱に入れる組み合わせの問題と本質的に同じとみなすことができる。そのため、以下ではこうした場合の数を全てn個の玉とk個の箱の問題として考える。
n個の玉をk個の箱に入れる場合の数は、状況によって12パターンの問題設定が考えられる。
これらの12パターンのそれぞれの場合の数の求め方については、以下のサイトが詳しい。
写像の個数（写像12相）
n 個の玉を区別するのかしないのか，k 個の箱を区別するのかしないのかで4通りの問題設定が考えられます。さらに，条件として，
1：何も条件がない場合
2：全ての箱の中身が一つ以下
3：全ての箱の中身が一つ以上
という3つの条件が考えられ，全部で12通りの問題設定が与えられています。
僕が勤しんでいる競技プログラミングでもこれらの12通りの問題に帰着できる場面は多い。
その際、全組み合わせを列挙できる関数があれば便利だと思ったので、これらのパターンのいくつかについて関数を作成した。
n個の区別しない玉をk個の区別する箱に入れる組み合わせ
n+1のしきいを入れるスペースからk-1個を選ぶ問題に帰着できる（1枚しきいを入れるたびにスペースは1増える）ので、数式としては$_{n+k-1}\mathrm{C} _{k-1}$として表せる。
全組み合わせを列挙する関数は以下の通り。
def n_same_k_different(n, k):
ans = []
if k == 1:
return [[n]]
for i in range(n+1):
# n個の玉は区別せず、k個の箱だけ区別する関数。
for j in n_same_k_different(n-i, k-1):
ans.append([i]+j)
return ans
n_same_k_different(3, 2)
[[0, 3], [1, 2], [2, 1], [3, 0]]
n個の区別しない玉をk個の区別しない箱に入れる組み合わせ
n個の区別しない玉をk個の区別しない箱に入れる場合の数は分割数といい、これを簡単に数式で表現する方法はない。
漸化式としては、nをkで分割する組み合わせ総数をを$P(n, k)$とすると、
- 0が含まれる場合、0を除いた組み合わせ総数なので、$P(n, k-1)$と等しい。
- 0が含まれない場合、それぞれから1を引いた組み合わせ総数なので$P(n-k, k)$と等しい。
よって、$P(n, k)=P(n, k-1)+P(n-k, k)$
これも再帰関数で表現できる。
def divide_number(n, k):
if k == 1:
return [[n]]
ans = []
for i in divide_number(n, k-1):
ans.append([0] + i)
if n >= k:
for j in divide_number(n-k, k):
ans.append([l+1 for l in j])
return ans
divide_number(5, 3)
def divide_combination(n, k):
dp = [1] * (n + 1)
for i in range(1, k):
for j in range(i+1, n+1):
dp[j] += dp[j - i -1]
return dp[-1]
組み合わせ数だけ出力。
[[0, 0, 5], [0, 1, 4], [0, 2, 3], [1, 1, 3], [1, 2, 2]]
ちなみに。r以上の数が含まれない組み合わせ。
import math
d = 0
def divide_number(n, k, d, r):
print(d)
if k == 1:
return [[n]]
ans = []
if math.ceil(n // (k-1)) < r - d:
for i in divide_number(n, k-1, d):
ans.append([0] + i)
if n >= k:
if math.ceil(n // k) < r - d:
d += 1
for j in divide_number(n-k, k, d):
ans.append([l+1 for l in j])
return ans
def divide_combination(n, k, r):
dp = [1] * (n + 1)
for i in range(1, k):
for j in range(i+1, n+1):
if i >1:
if math.ceil(j // (i-1)) > r:
dp[j] = dp[j - i -1]
continue
dp[j] += dp[j - i -1]
return dp[-1]
数だけ出力。全てr未満の制約付き。