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章(両替する方法を数える)、練習問題(パズル問題2)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3

count = 0


def make_smart_change(
        money: list, target: int, highest: int, solution: list = []) -> None:
    '''
    >>> make_smart_change([(1, 3), (2, 3), (5, 1)], 6, 1)
    [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 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, new_solution)
    return None


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

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

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