Puzzle DE Programming

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)」といいます。モンモール数は次の漸化式で求めることができます。

それでは問題です。次の関数を Python で作ってください。

1. 要素が n 個 (0, 1, ..., n - 1) の完全順列を生成する関数 derangement(fn, n)
2. 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)」といいます。ベル数は次の漸化式で求めることができます。

それでは問題です。次の関数を Python で作ってください。

1. 集合 xs の分割の仕方をすべて求める高階関数 parititon_of_set(fn, xs)
2. n 番目のベル数を求める関数 bell_number(n)
3. k 個の要素をもつ集合 xs を要素数が等しい m 個の部分集合に分割することを考えます。部分集合の要素数 n は k / m になります。
   分割の仕方をすべて求める高階関数 group_partition(fn, n, m, xs) を定義してください。
4. 集合 xs を group_partition() で分割するとき、その仕方の総数を求める関数 group_partition_number(xs, n, m) を定義してください。引数 n は部分集合の要素数、m は部分集合の個数です。

●解答１

集合を分割するアルゴリズムは簡単です。たとえば、n -1 個の要素 x1, ..., xn-1 を持つ集合を分割したところ、i 個の部分集合 S1, ..., Si が生成されたとしましょう。ここに、n 番目の要素 xn を追加すると、要素が n 個の集合を分割することができます。

新しい要素を追加する場合は次に示す手順で行います。

1. 部分集合 S_k (k = 1 から i まで) に要素 xn を追加する
2. 新しい部分集合 S_i+1 (要素が xn だけの集合) を生成する

簡単な例を示しましょう。次の図を見てください。

[] ─ [[1]] ─┬─ [[1, 2]] ─┬─ [[1, 2, 3]]
              │              │
              │              └─ [[1, 2], [3]]
              │
              └─ [[1], [2]] ─┬─ [[1, 3] [2]]
                                │
                                ├─ [[1,], [2, 3]]
                                │
                                └─ [[1], [2], [3]]

        図 : 集合 [1, 2, 3] を分割する

部分集合を格納する配列を用意します。最初、部分集合は空集合なので空の配列に初期化します。次に、要素 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]]

●解答４

グループ分けの総数は次の式で求めることができます。

たとえば、n = 3, m = 5 の場合は次のようになります。

これをそのままプログラムすると次のようになります。

リスト : グループ分けの総数

# 階乗
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)