Algorithm - Python - メモリは役に立つ(両替方法、異なる解の個数、貪欲アルゴリズム、辞書の作成と検索、例外、再帰探索でのメモ化)

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の18章(メモリは役に立つ)、練習問題(問題5)の解答を求めてみる。

コード

Python 3

#!/usr/bin/env python3

count = 0


def make_smart_change(
        bills: list, target: int, highest: int, solution: list = []) -> None:
    '''
    >>> make_smart_change([1, 2, 5], 6, 1)
    [1, 1, 1, 1, 1, 1]
    [1, 1, 1, 1, 2]
    [1, 1, 2, 2]
    [1, 5]
    [2, 2, 2]
    '''
    global count
    total = sum(solution)
    if total == target:
        print(solution)
        count += 1
        return None
    if total > target:
        return None
    for bill in bills:
        if bill >= highest:
            new_solution = solution[:] + [bill]
            make_smart_change(bills, target, bill, new_solution)
    return None


def make_smart_change_count(bills: list, size: int, target: int) -> int:
    '''
    >>> make_smart_change_count([1, 2, 5], 3, 6)
    5
    >>> make_smart_change_count([1, 2, 5, 10], 4, 16)
    25
    '''
    if target == 0:
        return 1
    if target < 0:
        return 0
    if size == 0:
        return 0
    count1 = make_smart_change_count(bills, size-1, target)
    count2 = make_smart_change_count(bills, size, target - bills[size-1])
    return count1 + count2


def make_smart_change_count_memoized(
        bills: list, size: int, target: int, memo: {}) -> int:
    '''
    >>> make_smart_change_count_memoized([1, 2, 5], 3, 6, {})
    5
    >>> make_smart_change_count_memoized([1, 2, 5, 10], 4, 16, {})
    25
    '''
    if (size, target) in memo:
        return memo[(size, target)]
    if target == 0:
        return 1
    if target < 0:
        return 0
    if size == 0:
        return 0
    count1 = make_smart_change_count_memoized(bills, size-1, target, memo)
    count2 = make_smart_change_count_memoized(
        bills, size, target - bills[size-1], memo)

    count0 = count1 + count2
    memo[(size, target)] = count0
    return count0


if __name__ == '__main__':
    import doctest
    doctest.testmod()
    count = 0
    make_smart_change([1, 2, 5], 6, 1)
    print(count, count == 5)
    count = 0
    make_smart_change([1, 2, 5, 10], 16, 1)
    print(count, count == 25)

    import time
    bills = list(range(1, 11))
    target = 100
    print(f'紙幣: {bills}、目標値: {target}')
    start = time.time()
    c = make_smart_change_count(bills, len(bills), target)
    t = time.time() - start
    print(f'メモ化無し: {c} {t}s')
    start = time.time()
    c = make_smart_change_count_memoized(bills, len(bills), target, {})
    t = time.time() - start
    print(f'メモ化有り: {c} {t}s')

入出力結果(Terminal、cmd(コマンドプロンプト)、Jupyter(IPython))

$ python3 sample5.py -v
Trying:
    make_smart_change([1, 2, 5], 6, 1)
Expecting:
    [1, 1, 1, 1, 1, 1]
    [1, 1, 1, 1, 2]
    [1, 1, 2, 2]
    [1, 5]
    [2, 2, 2]
ok
Trying:
    make_smart_change_count([1, 2, 5], 3, 6)
Expecting:
    5
ok
Trying:
    make_smart_change_count([1, 2, 5, 10], 4, 16)
Expecting:
    25
ok
Trying:
    make_smart_change_count_memoized([1, 2, 5], 3, 6, {})
Expecting:
    5
ok
Trying:
    make_smart_change_count_memoized([1, 2, 5, 10], 4, 16, {})
Expecting:
    25
ok
1 items had no tests:
    __main__
3 items passed all tests:
   1 tests in __main__.make_smart_change
   2 tests in __main__.make_smart_change_count
   2 tests in __main__.make_smart_change_count_memoized
5 tests in 4 items.
5 passed and 0 failed.
Test passed.
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 2]
[1, 1, 2, 2]
[1, 5]
[2, 2, 2]
5 True
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2]
[1, 1, 1, 1, 1, 1, 1, 2, 2, 5]
[1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]
[1, 1, 1, 1, 1, 1, 5, 5]
[1, 1, 1, 1, 1, 1, 10]
[1, 1, 1, 1, 1, 2, 2, 2, 5]
[1, 1, 1, 1, 2, 2, 2, 2, 2, 2]
[1, 1, 1, 1, 2, 5, 5]
[1, 1, 1, 1, 2, 10]
[1, 1, 1, 2, 2, 2, 2, 5]
[1, 1, 2, 2, 2, 2, 2, 2, 2]
[1, 1, 2, 2, 5, 5]
[1, 1, 2, 2, 10]
[1, 2, 2, 2, 2, 2, 5]
[1, 5, 5, 5]
[1, 5, 10]
[2, 2, 2, 2, 2, 2, 2, 2]
[2, 2, 2, 5, 5]
[2, 2, 2, 10]
25 True
紙幣: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]、目標値: 100
メモ化無し: 6292069 33.50895714759827s
メモ化有り: 6292069 0.0007131099700927734s
$