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 (著)、黒川 利明 (翻訳)、オライリージャパン)の15章(両替する方法を数える)、練習問題(問題3)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3

count = 0


def make_smart_change(money: list, target: int, highest: int,
                      minimum_solution: list, solution: list = []) -> None:
    '''
    >>> minimum_solution = []
    >>> make_smart_change([(1, 3), (2, 3), (5, 1)], 6, 1, minimum_solution)
    >>> print(minimum_solution)
    [1, 5]
    '''
    global count
    total = sum(solution)
    if total == target:
        if len(minimum_solution) == 0 or len(solution) < len(minimum_solution):
            minimum_solution.clear()
            for n in solution:
                minimum_solution.append(n)
            count += 1
            return None
    if total > target:
        return None
    for i, (bill, rest) in enumerate(money):
        if bill >= highest:
            new_solution = solution[:] + [bill]
            rest -= 1
            if rest == 0:
                new_money = money[1:]
            else:
                new_money = money[:]
                new_money[i] = (bill, rest - 1)
            make_smart_change(new_money, target, bill,
                              minimum_solution, new_solution)
    return None


if __name__ == '__main__':
    import doctest
    doctest.testmod()

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

$ ./sample3.py -v
Trying:
    minimum_solution = []
Expecting nothing
ok
Trying:
    make_smart_change([(1, 3), (2, 3), (5, 1)], 6, 1, minimum_solution)
Expecting nothing
ok
Trying:
    print(minimum_solution)
Expecting:
    [1, 5]
ok
1 items had no tests:
    __main__
1 items passed all tests:
   3 tests in __main__.make_smart_change
3 tests in 2 items.
3 passed and 0 failed.
Test passed.
$