小町算 (2)
[問題１] 小町算
1 から 9 までの数字を順番に並べ、間に + と - を補って値が N になる式を作ってください。 ただし、1 の先頭に - 符号は付けないことにします。
[問題２] 小町算虫食い算- A から I の場所に 1 から 9 までの数字を 1 回ずつ入れて式を完成させてください。
ＡＢＣＤＥ÷ＦＧＨＩ＝１５
- A から G の場所に数字 1, 3, 4, 5, 7, 8, 9 を 1 回ずつ入れて式を完成させてください。
ＡＢＣ２６÷ＤＥＦＧ＝２６
次に示す式を完成させてください。□にはどんな数字を入れてもかまいません。
(A) は 参考文献 12 に掲載されています。ほかに面白い式はないかプログラムを作って探してみたところ、(B), (C), (D) を見つけました。解があることは保証しますが、手で解くにはちょっと難しいかもしれません。興味のある方は挑戦してみてください。
●プログラムリスト
リスト : 小町算(2)
from itertools import permutations
# 式の表示
def print_expr(expr, ans):
for x in expr:
print(x, end=' ')
print(f'= {ans}')
# 式の計算
def calc_expr(expr):
n = expr[0]
for i in range(1, len(expr), 2):
if expr[i] == '+':
n += expr[i + 1]
else:
n -= expr[i + 1]
return n
# 式の生成
def make_expr(n, expr, ans):
if n == 10:
if calc_expr(expr) == ans:
print_expr(expr, ans)
else:
make_expr(n + 1, expr + ['+', n], ans)
make_expr(n + 1, expr + ['-', n], ans)
m = expr[-1]
expr[-1] = m * 10 + n
make_expr(n + 1, expr, ans)
expr[-1] = m
# 小町算の解法
def komachi_solver(ans):
make_expr(2, [1], ans)
# 小町虫食い算
def komachi21():
for xs in permutations('123456789'):
n = int(''.join(xs[:5]))
m = int(''.join(xs[5:]))
if n % m == 0 and n // m == 15:
print(f'{n} / {m} = 15')
def komachi22():
for xs in permutations('1345789'):
n = int(''.join(xs[:3])) * 100 + 26
m = int(''.join(xs[3:]))
if n % m == 0 and n // m == 26:
print(f'{n} / {m} = 26')
# 小町数
def komachi3a():
for n in range(10000, 100000):
if 123456789 % n == 0:
m = 123456789 // n
if m >= 10000 and n < m:
print(f'{n} * {m} = 123456789')
def komachi3b():
for n in range(1000, 10000):
if 123456789 % n == 0:
m = 123456789 // n
print(f'{n} * {m} = 123456789')
def komachi3c():
for n in range(1000, 10000):
if 987654321 % n == 0:
m = 987654321 // n
print(f'{n} * {m} = 987654321')
def komachi3d():
for n in range(100, 1000):
if 987654321 % n == 0:
m = 987654321 // n
print(f'{n} * {m} = 987654321')
●2 になる式
1 + 2 + 34 - 5 - 6 - 7 - 8 - 9 1 + 23 + 4 + 56 + 7 - 89 1 - 2 + 34 + 56 - 78 - 9 12 + 3 + 4 + 5 + 67 - 89 12 + 3 + 4 - 5 - 6 - 7 - 8 + 9 12 + 3 - 4 + 5 - 6 - 7 + 8 - 9 12 + 3 - 4 - 5 + 6 + 7 - 8 - 9 12 - 3 + 4 + 5 - 6 + 7 - 8 - 9 12 - 3 - 4 - 5 - 6 + 7 - 8 + 9 123 + 4 - 56 - 78 + 9 123 - 45 + 6 + 7 - 89
●14 になる式
1 + 2 + 34 - 5 + 6 - 7 - 8 - 9 1 + 2 - 34 - 5 + 67 - 8 - 9 1 - 2 + 34 - 5 - 6 - 7 + 8 - 9 1 - 2 - 3 - 45 - 6 + 78 - 9 1 - 23 + 4 + 56 - 7 - 8 - 9 1 - 23 - 4 - 56 + 7 + 89 1 - 23 - 45 - 6 + 78 + 9 12 + 3 + 4 - 5 + 6 - 7 - 8 + 9 12 + 3 + 4 - 5 - 6 + 7 + 8 - 9 12 + 3 - 4 + 5 + 6 - 7 + 8 - 9 12 + 34 - 56 + 7 + 8 + 9 12 - 3 + 4 + 5 + 6 + 7 - 8 - 9 12 - 3 - 4 + 5 - 6 - 7 + 8 + 9 12 - 3 - 4 - 5 + 6 + 7 - 8 + 9 12 - 3 - 45 + 67 - 8 - 9
●15 になる式
1 + 2 + 3 + 4 + 5 + 6 - 7 - 8 + 9 1 + 2 + 3 + 4 + 5 - 6 + 7 + 8 - 9 1 + 2 + 3 - 4 - 5 - 6 + 7 + 8 + 9 1 + 2 + 3 - 4 - 56 + 78 - 9 1 + 2 - 3 + 4 - 5 + 6 - 7 + 8 + 9 1 + 2 - 3 + 45 - 6 - 7 - 8 - 9 1 + 2 - 3 - 4 + 5 + 6 + 7 - 8 + 9 1 + 2 - 34 + 56 + 7 - 8 - 9 1 + 23 + 4 + 5 + 6 - 7 - 8 - 9 1 + 23 + 4 + 56 - 78 + 9 1 + 23 - 4 - 5 + 6 - 7 - 8 + 9 1 + 23 - 4 - 5 - 6 + 7 + 8 - 9 1 - 2 + 3 + 4 + 5 - 6 - 7 + 8 + 9 1 - 2 + 3 + 4 - 5 + 6 + 7 - 8 + 9 1 - 2 + 3 - 4 + 5 + 6 + 7 + 8 - 9 1 - 2 + 3 - 4 - 5 - 67 + 89 1 - 2 - 3 - 4 + 5 - 6 + 7 + 8 + 9 1 - 2 - 34 + 56 - 7 - 8 + 9 12 + 34 + 56 - 78 - 9 123 -45 + 6 - 78 + 9
●16 になる式
1 + 2 + 34 - 5 - 6 + 7 - 8 - 9 1 - 2 + 34 + 5 + 67 - 89 1 - 2 + 34 - 5 - 6 - 7 - 8 + 9 12 + 3 + 4 - 5 - 6 + 7 - 8 + 9 12 + 3 - 4 + 5 + 6 - 7 - 8 + 9 12 + 3 - 4 + 5 - 6 + 7 + 8 - 9 12 - 3 + 4 + 5 + 6 - 7 + 8 - 9 12 - 3 - 4 - 5 + 6 - 7 + 8 + 9
●17 になる式
1 + 2 + 3 + 4 + 5 - 6 + 7 - 8 + 9 1 + 2 + 3 + 4 - 5 + 6 + 7 + 8 - 9 1 + 2 - 3 + 4 - 5 - 6 + 7 + 8 + 9 1 + 2 - 3 + 4 - 56 + 78 - 9 1 + 2 - 3 - 4 + 5 + 6 - 7 + 8 + 9 1 + 2 - 34 + 56 - 7 + 8 - 9 1 + 23 + 4 + 5 - 6 + 7 - 8 - 9 1 + 23 - 4 - 5 - 6 + 7 - 8 + 9 1 - 2 + 3 + 4 - 5 + 6 - 7 + 8 + 9 1 - 2 + 3 + 45 - 6 - 7 - 8 - 9 1 - 2 + 3 - 4 + 5 + 6 + 7 - 8 + 9 1 - 2 - 3 + 4 + 5 + 6 + 7 + 8 - 9 1 - 2 - 3 + 4 - 5 - 67 + 89 1 - 2 - 3 - 4 - 5 + 6 + 7 + 8 +9 1 - 2 - 3 - 45 + 67 + 8 - 9 1 - 23 + 4 + 5 + 6 + 7 + 8 + 9 1 - 23 - 45 + 67 + 8 + 9
●18 になる式
1 + 2 + 34 - 5 - 6 - 7 + 8 - 9 1 + 2 - 3 - 45 - 6 + 78 - 9 1 - 2 - 3 - 4 - 56 - 7 + 89 12 + 3 + 4 - 5 - 6 - 7 + 8 + 9 12 + 3 - 4 + 5 - 6 + 7 - 8 + 9 12 + 3 - 4 - 5 + 6 + 7 + 8 - 9 12 - 3 + 4 + 5 + 6 - 7 - 8 + 9 12 - 3 + 4 + 5 - 6 + 7 + 8 - 9 12 - 3 - 4 - 5 - 6 + 7 + 8 + 9 12 - 3 - 4 - 56 + 78 - 9 12 - 34 - 56 + 7 + 89
●20 になる式
1 + 2 + 34 + 5 + 67 - 89 1 + 2 + 34 - 5 - 6 - 7 - 8 + 9 1 - 2 + 3 - 45 - 6 + 78 - 9 1 - 2 + 34 + 5 + 6 - 7 - 8 - 9 1 - 2 + 34 + 56 - 78 + 9 1 - 2 - 34 + 5 + 67 - 8 - 9 1 - 23 - 4 + 56 + 7 - 8 - 9 12 + 3 + 4 + 5 + 6 + 7 - 8 - 9 12 + 3 - 4 + 5 - 6 - 7 + 8 + 9 12 + 3 - 4 - 5 + 6 + 7 - 8 + 9 12 + 3 - 45 + 67 - 8 - 9 12 + 34 + 56 + 7 - 89 12 - 3 + 4 + 5 - 6 + 7 - 8 + 9 12 - 3 + 4 - 5 + 6 + 7 + 8 - 9 123 + 4 - 5 - 6 - 7 - 89
●200 になる式
1 + 234 - 5 - 6 - 7 - 8 - 9 123 + 4 + 5 + 67 - 8 + 9 123 - 4 + 5 - 6 - 7 + 89
●小町虫食い算の解答１
２７９４５÷１８６３＝１５ ９２７４５÷６１８３＝１５
●小町虫食い算の解答２
８９７２６÷３４５１＝２６
●小町数の解答
(A) １０８２１×１１４０９＝１２３４５６７８９
(B) ３６０７×３４２２７＝１２３４５６７８９
３８０３×３２４６３＝１２３４５６７８９
(C) ２６０１×３７９７２１＝９８７６５４３２１
(D) １５３×６４５５２５７＝９８７６５４３２１
２８９×３４１７４８９＝９８７６５４３２１
８６７×１１３９１６３＝９８７６５４３２１
完全順列とモンモール数
n 個の整数 0, 1, ..., n - 1 の順列を考えます。このとき、i 番目の要素が整数 i ではない順列を「完全順列 (derangement)」といいます。たとえば、0, 1, 2 の完全順列は次の 2 通りになります。
1, 2, 0 2, 0, 1
整数 0 は 0 番目に、1 は 1 番目に、 2 は 2 番目に現れていません。これが完全順列になります。そして、完全順列の総数を「モンモール数 (Montmort number)」といいます。モンモール数は次の漸化式で求めることができます。
A1 = 0 A2 = 1 An = (n - 1) * (An-1 + An-2) # n >= 3
それでは問題です。次の関数を Python で作ってください。
- 要素が n 個 (0, 1, ..., n - 1) の完全順列を生成する関数 derangement(fn, n)
- n 番目のモンモール数を求める関数 montmort(n)
●解答１
リスト : 完全順列
def derangement(fn, n, ps = []):
if len(ps) == n:
fn(ps[:])
else:
for x in range(n):
if x == len(ps) or x in ps: continue
ps.append(x)
derangement(fn, n, ps)
ps.pop()
>>> derangement(print, 3) [1, 2, 0] [2, 0, 1] >>> derangement(print, 4) [1, 0, 3, 2] [1, 2, 3, 0] [1, 3, 0, 2] [2, 0, 3, 1] [2, 3, 0, 1] [2, 3, 1, 0] [3, 0, 1, 2] [3, 2, 0, 1] [3, 2, 1, 0]
derangement() は順列を生成するプログラムに条件を追加するだけです。数字 x を選択するとき、その値が位置 len(ps) と等しくないことを確認するだけです。
●解答２
リスト : モンモール数
def montmort(n):
if n == 1:
return 0
elif n == 2:
return 1
else:
return (n - 1) * (montmort(n - 1) + montmort(n - 2))
# 別解
def montmort_loop(n):
a, b = 0, 1
for i in range(1, n):
a, b = b, (i + 1) * (a + b)
>>> for x in range(1, 11): ... print(montmort(x), montmort_loop(x)) ... 0 0 1 1 2 2 9 9 44 44 265 265 1854 1854 14833 14833 133496 133496 1334961 1334961 >>> montmort_loop(20) 895014631192902121 >>> montmort_loop(30) 97581073836835777732377428235481 >>> montmort_loop(40) 300158458444475693321518926221316715906770469041 >>> montmort_loop(50) 11188719610782480504630258070757734324011354208865721592720336801
関数 montmort() は公式をそのままプログラムしただけです。二重再帰になっているので、実行速度はとても遅くなります。これを繰り返しに変換すると別解のようになります。考え方はフィボナッチ数列と同じです。累積変数 a に i 番目の値を、b に i + 1 番目の値を保存しておきます。すると、i + 2 番目の値は (i + 1) * (a + b)) で計算することができます。あとは、b の値を a に、新しい値を b にセットして処理を繰り返すだけです。
集合の分割とベル数
Python のリストで表した集合 xs を分割することを考えます。たとえば、集合 [1, 2, 3] は次のように分割することができます。
1 分割 : [[1, 2, 3]] 2 分割 : [[1, 2], [3]], [[1, 3], [2]], [[1], [2, 3]] 3 分割 ; [[1], [2], [3]]
このように、分割した集合 ys は元の集合 xs の部分集合になります。分割した部分集合の積は空集合になり、分割した部分集合のすべての和を求めると元の集合になります。そして、集合を分割する方法の総数を「ベル数 (Bell Number)」といいます。ベル数は次の漸化式で求めることができます。
B(0) = 1
n
B(n+1) = Σ nＣk * B(k) # n >= 1
k=0
それでは問題です。次の関数を Python で作ってください。
- 集合 xs の分割の仕方をすべて求める高階関数 parititon_of_set(fn, xs)
- n 番目のベル数を求める関数 bell_number(n)
- k 個の要素をもつ集合 xs を要素数が等しい m 個の部分集合に分割することを考えます。部分集合の要素数 n は k / m になります。
分割の仕方をすべて求める高階関数 group_partition(fn, n, m, xs) を定義してください。 - 集合 xs を group_partition() で分割するとき、その仕方の総数を求める関数 group_partition_number(xs, n, m) を定義してください。引数 n は部分集合の要素数、m は部分集合の個数です。
●解答１
集合を分割するアルゴリズムは簡単です。たとえば、n -1 個の要素 x1, ..., xn-1 を持つ集合を分割したところ、i 個の部分集合 S1, ..., Si が生成されたとしましょう。ここに、n 番目の要素 xn を追加すると、要素が n 個の集合を分割することができます。
新しい要素を追加する場合は次に示す手順で行います。
- 部分集合 Sk (k = 1 から i まで) に要素 xn を追加する
- 新しい部分集合 Si+1 (要素が xn だけの集合) を生成する
簡単な例を示しましょう。次の図を見てください。
部分集合を格納する配列を用意します。最初、部分集合は空集合なので空の配列に初期化します。次に、要素 1 を追加します。部分集合は空なので、手順 1 は適用できません。手順 2 を適用して新しい部分集合 [1] を追加します。
次に要素 2 を追加します。[[1]] に 手順 1 を適用すると、部分集合 [1] に要素を追加して [[1, 2]] になります。手順 2 を適用すると、新しい部分集合 [2] を追加して [[1], [2]] になります。最後に 3 を追加します。[[1, 2]] に手順 1 を適用すると [[1, 2, 3]] に、手順 2 を適用すると [[1, 2], [3]] になります。[[1], [2]] に手順 1 を適用すると [[1, 3] [2]] と [[1], [2, 3]] になり、手順 2 を適用すると [[1], [2], [3]] になります。
このように、簡単な方法で集合を分割することができます。実際にプログラムを作る場合、上図を木と考えて、深さ優先で木をたどると簡単です。次のリストを見てください。
リスト : 集合の分割
def partition_of_set(fn, xs, j = 0, a = []):
if len(xs) == j:
fn(a)
else:
for i in range(len(a)):
a[i].append(xs[j])
partition_of_set(fn, xs, j + 1, a)
a[i].pop()
a.append([xs[j]])
partition_of_set(fn, xs, j + 1, a)
a.pop()
関数 partition_of_set() の引数 xs が集合、引数 j が追加する要素の添字、生成した部分集合は累積変数 a に格納します。j が len(xs) と等しい場合、追加する要素がなくなったので fn(a) を評価します。要素がある場合、i 番目の部分集合に要素 ls[j] を追加して、partition_of_set() を再帰呼び出しします。すべての部分集合に要素を追加したら、xs[j] を要素として持つ部分集合を生成して累積変数 a に追加します。
簡単な実行例を示します。
>>> partition_of_set(print, [1,2,3]) [[1, 2, 3]] [[1, 2], [3]] [[1, 3], [2]] [[1], [2, 3]] [[1], [2], [3]] >>> partition_of_set(print, [1,2,3,4]) [[1, 2, 3, 4]] [[1, 2, 3], [4]] [[1, 2, 4], [3]] [[1, 2], [3, 4]] [[1, 2], [3], [4]] [[1, 3, 4], [2]] [[1, 3], [2, 4]] [[1, 3], [2], [4]] [[1, 4], [2, 3]] [[1], [2, 3, 4]] [[1], [2, 3], [4]] [[1, 4], [2], [3]] [[1], [2, 4], [3]] [[1], [2], [3, 4]] [[1], [2], [3], [4]]
●解答２
リスト : ベル数
# 組み合わせの数
def comb(n, r):
if n == r or r == 0: return 1
return comb(n, r - 1) * (n - r + 1) // r
# ベル数
def bell_number(n):
bs = [1]
for i in range(n):
a = 0
for k, b in enumerate(bs):
a += comb(i, k) * b
bs.append(a)
return bs[-1]
関数 bell_number() は公式をそのままプログラムするだけです。累積変数 bs にベル数を格納します。nＣk は関数 comb() で求めます。nＣk * B(k) の総和は 2 番目の for ループで計算します。最後に、bs の末尾要素を return で返します。
簡単な実行例を示します。
>>> for x in range(11): ... print(bell_number(x)) ... 1 1 2 5 15 52 203 877 4140 21147 115975 >>> bell_number(20) 51724158235372 >>> bell_number(30) 846749014511809332450147 >>> bell_number(40) 157450588391204931289324344702531067 >>> bell_number(50) 185724268771078270438257767181908917499221852770
●解答３
リスト : 集合のグループ分け
def group_partition(fn, xs, n, m, j = 0, a = []):
if len(xs) == j:
fn(a)
else:
for i in range(len(a)):
if len(a[i]) >= n: continue
a[i].append(xs[j])
group_partition(fn, xs, n, m, j + 1, a)
a[i].pop()
if len(a) < m:
a.append([xs[j]])
group_partition(fn, xs, n, m, j + 1, a)
a.pop()
group_partition() は partition_of_set() を改造するだけで簡単に作成することができます。生成する部分集合の大きさを n に、部分集合の個数を m に制限するだけです。i 番目の部分集合に要素を追加する場合、len(a[i]) が n 未満であることをチェックします。新しい部分集合を追加する場合、len(a) が m 未満であることをチェックします。これで集合をグループに分けることができます。
簡単な実行例を示します。
>>> group_partition(print, [1,2,3,4], 2, 2) [[1, 2], [3, 4]] [[1, 3], [2, 4]] [[1, 4], [2, 3]] >>> group_partition(print, [1,2,3,4,5,6], 2, 3) [[1, 2], [3, 4], [5, 6]] [[1, 2], [3, 5], [4, 6]] [[1, 2], [3, 6], [4, 5]] [[1, 3], [2, 4], [5, 6]] [[1, 3], [2, 5], [4, 6]] [[1, 3], [2, 6], [4, 5]] [[1, 4], [2, 3], [5, 6]] [[1, 5], [2, 3], [4, 6]] [[1, 6], [2, 3], [4, 5]] [[1, 4], [2, 5], [3, 6]] [[1, 4], [2, 6], [3, 5]] [[1, 5], [2, 4], [3, 6]] [[1, 6], [2, 4], [3, 5]] [[1, 5], [2, 6], [3, 4]] [[1, 6], [2, 5], [3, 4]] >>> group_partition(print, [1,2,3,4,5,6], 3, 2) [[1, 2, 3], [4, 5, 6]] [[1, 2, 4], [3, 5, 6]] [[1, 2, 5], [3, 4, 6]] [[1, 2, 6], [3, 4, 5]] [[1, 3, 4], [2, 5, 6]] [[1, 3, 5], [2, 4, 6]] [[1, 3, 6], [2, 4, 5]] [[1, 4, 5], [2, 3, 6]] [[1, 4, 6], [2, 3, 5]] [[1, 5, 6], [2, 3, 4]]
●解答４
グループ分けの総数は次の式で求めることができます。
k = n * m kＣn * k-nＣn * k-2*nＣn * ... * 2*nＣn * nＣn / m!
たとえば、n = 3, m = 5 の場合は次のようになります。
15Ｃ3 * 12Ｃ3 * 9Ｃ3 * 6Ｃ3 * 3Ｃ3 / 5! = 1401400
これをそのままプログラムすると次のようになります。
リスト : グループ分けの総数
# 階乗
def fact(n):
if n == 0: return 1
return n * fact(n - 1)
# グループ分けの総数
def group_partition_number(n, m):
a = 1
for k in range(n * m, 0, -n):
a *= comb(k, n)
return a // fact(m)
階乗は関数 fact() で、組み合わせの個数は関数 comb() で計算します。要素の個数を変数 k にセットし、累積変数 a に comb(k, n) を乗算します。あとは k から n を減算し、k が 0 でなければ処理を繰り返すだけです。最後に a // fact(m) を計算して返します。
簡単な実行例を示します。
>>> group_partition_number(2, 2) 3 >>> group_partition_number(2, 3) 15 >>> group_partition_number(3, 2) 10 >>> group_partition_number(3, 3) 280 >>> group_partition_number(3, 4) 15400 >>> group_partition_number(3, 5) 1401400
●プログラムリスト
#
# number2.py : 数字のパズル (2)
#
# Copyright (C) 2022 Makoto Hiroi
#
from itertools import permutations
# 小町算
# 式の表示
def print_expr(expr, ans):
for x in expr:
print(x, end=' ')
print(f'= {ans}')
# 式の計算
def calc_expr(expr):
n = expr[0]
for i in range(1, len(expr), 2):
if expr[i] == '+':
n += expr[i + 1]
else:
n -= expr[i + 1]
return n
# 式の生成
def make_expr(n, expr, ans):
if n == 10:
if calc_expr(expr) == ans:
print_expr(expr, ans)
else:
make_expr(n + 1, expr + ['+', n], ans)
make_expr(n + 1, expr + ['-', n], ans)
m = expr[-1]
expr[-1] = m * 10 + n
make_expr(n + 1, expr, ans)
expr[-1] = m
# 小町算の解法
def komachi_solver(ans):
make_expr(2, [1], ans)
# 小町虫食い算
def komachi21():
for xs in permutations('123456789'):
n = int(''.join(xs[:5]))
m = int(''.join(xs[5:]))
if n % m == 0 and n // m == 15:
print(f'{n} / {m} = 15')
def komachi22():
for xs in permutations('1345789'):
n = int(''.join(xs[:3])) * 100 + 26
m = int(''.join(xs[3:]))
if n % m == 0 and n // m == 26:
print(f'{n} / {m} = 26')
# 小町数
def komachi3a():
for n in range(10000, 100000):
if 123456789 % n == 0:
m = 123456789 // n
if m >= 10000 and n < m:
print(f'{n} * {m} = 123456789')
def komachi3b():
for n in range(1000, 10000):
if 123456789 % n == 0:
m = 123456789 // n
print(f'{n} * {m} = 123456789')
def komachi3c():
for n in range(1000, 10000):
if 987654321 % n == 0:
m = 987654321 // n
print(f'{n} * {m} = 987654321')
def komachi3d():
for n in range(100, 1000):
if 987654321 % n == 0:
m = 987654321 // n
print(f'{n} * {m} = 987654321')
# 完全順列
def derangement(fn, n, ps = []):
if len(ps) == n:
fn(ps[:])
else:
for x in range(n):
if x == len(ps) or x in ps: continue
ps.append(x)
derangement(fn, n, ps)
ps.pop()
# モンモール数
def montmort(n):
if n == 1:
return 0
elif n == 2:
return 1
else:
return (n - 1) * (montmort(n - 1) + montmort(n - 2))
def montmort_loop(n):
a, b = 0, 1
for i in range(1, n):
a, b = b, (i + 1) * (a + b)
return a
# 集合の分割
def partition_of_set(fn, xs, j = 0, a = []):
if len(xs) == j:
fn(a)
else:
for i in range(len(a)):
a[i].append(xs[j])
partition_of_set(fn, xs, j + 1, a)
a[i].pop()
a.append([xs[j]])
partition_of_set(fn, xs, j + 1, a)
a.pop()
# 組み合わせの数
def comb(n, r):
if n == r or r == 0: return 1
return comb(n, r - 1) * (n - r + 1) // r
# ベル数
def bell_number(n):
bs = [1]
for i in range(n):
a = 0
for k, b in enumerate(bs):
a += comb(i, k) * b
bs.append(a)
return bs[-1]
# 集合のグループ分け
def group_partition(fn, xs, n, m, j = 0, a = []):
if len(xs) == j:
fn(a)
else:
for i in range(len(a)):
if len(a[i]) >= n: continue
a[i].append(xs[j])
group_partition(fn, xs, n, m, j + 1, a)
a[i].pop()
if len(a) < m:
a.append([xs[j]])
group_partition(fn, xs, n, m, j + 1, a)
a.pop()
# 階乗
def fact(n):
if n == 0: return 1
return n * fact(n - 1)
# グループ分けの総数
def group_partition_number(n, m):
a = 1
for k in range(n * m, 0, -n):
a *= comb(k, n)
return a // fact(m)