解決したい問題

手元に12個のピーマンがあり、その中からいくつか取り出して、150g入りの袋詰めで販売したいとします¹。つまりこれら12個のピーマンのどれを選べば良いのかを求める必要があります。

bell_peppers = [47, 36, 29, 24, 32, 24, 47, 51, 45, 20, 53, 37]

前提条件として、ピーマンを販売するにあたって表示されている内容量よりも実際の内容量が少ないということがあってはいけないので、150g以上の、150gに最も近い値を目指します。

これを実現するために、リストを引数として与えたら、そのリスト内の組み合わせで作れる150以上かつ150に最も近い値、およびその値を得るために選ぶべきピーマンの位置を返してくれる関数を作ります。

bell_pepper_search(bell_peppers)
# 返り値：(150, '000010001110')
# リスト内の5、9、10、11番目のピーマンを選ぶと150gとなることがわかる。

この問題は部分和問題と呼ばれていて、複数の解法がありますがここでは再帰を使った枝刈り全探索を行います²。

グローバル変数を使った再帰関数

再帰処理を行う際、再帰処理の中で計算した値などを一時的に保存したい場合があります。しかし関数の中で変数を宣言すると、関数が呼び出されるたびに新たなスコープで変数が宣言されるため、各再帰処理間での変数の共有はできません。値を各再帰処理間で共有する手段としてはグローバル変数を使うのが直感的かと思います。

overall_closest = sum(bell_peppers)  # 最終的に150以上の150に最も近い値が入る変数。
overall_closest_mask_bit_string = "1" * len(bell_peppers)  # 150以上の150に最も近い値を得るためのピーマンの位置を示してくれる文字列が入る変数。
def recursive_search_with_global(
    item_list,
    temp_sum=0,
    item_index=0,
    current_mask_bit_string="",
):
    global overall_closest
    global overall_closest_mask_bit_string
    if overall_closest == 150:  # ぴったり150となる組み合わせがすでに見つかっている場合は何もしない。
        pass
    elif item_index == len(item_list):  # リストの最後まで行った場合。
        if temp_sum >= 150:
            if abs(temp_sum - 150) <= abs(overall_closest - 150):  # 150により近い値を保持する。
                overall_closest = temp_sum
                overall_closest_mask_bit_string = current_mask_bit_string
            elif abs(temp_sum - 150) > abs(overall_closest - 150):
                pass
            else:
                raise Warning("You've missed something!")  # 再帰処理を書くにあたって条件を網羅できているかを確認するのに役立つ。
        elif temp_sum < 150:
            pass
        else:
            raise Warning("You've missed something!")
    elif item_index < len(item_list):  # リストの最後まで行っていない場合。
        if temp_sum >= 150:
            if abs(temp_sum - 150) <= abs(overall_closest - 150):
                overall_closest = temp_sum
                overall_closest_mask_bit_string = current_mask_bit_string
            elif abs(temp_sum - 150) > abs(overall_closest - 150):
                pass
            else:
                raise Warning("You've missed something!")
        elif temp_sum < 150:
            recursive_search_with_global(item_list, temp_sum, item_index + 1, current_mask_bit_string+"0")
            recursive_search_with_global(item_list, temp_sum+item_list[item_index], item_index + 1, current_mask_bit_string+"1")
        else:
            raise Warning("You've missed something!")
    else:
        raise Warning("You've missed something!")
    while len(overall_closest_mask_bit_string) < len(item_list):
        # リスト内の最後の要素にたどり着く前に150を超えた場合、末尾の0が抜けてしまうので0を足していく。
        overall_closest_mask_bit_string += "0"
    return overall_closest, overall_closest_mask_bit_string

ピーマンのリストを引数としてこの関数を呼び出してみます。

recursive_search_with_global(bell_peppers)
# (150, '000010001110')

ちょうど150gとなるピーマンの組み合わせが求まりました。これで1回目のピーマンの袋詰めは終わりです。

続けて2回目の袋詰めを行います。

bell_peppers_2 = [40, 40, 40, 40, 40]

連続して recursive_search_with_global 関数を呼び出してしまうと下のようになります。

recursive_search_with_global(bell_peppers_2)
# (150, '000010001110')

これはなぜかというと overall_closest および overall_closest_mask_bit_string には1回目の袋詰めで関数を呼び出した際の値が残っているからです。正しい結果を得るためにはこれらの変数に新しいリストを使った値を再代入してから関数を呼び出す必要があります。

overall_closest = sum(bell_peppers_2)
overall_closest_mask_bit_string = "1" * len(bell_peppers_2)
recursive_search_with_global(bell_peppers_2)
# (160, '11110')

また、今回のようにグローバル変数を操作している関数がひと目で分かるうちは大丈夫ですが、プログラム内の関数が増えてくると、どの関数が各グローバル変数をどの段階で操作しているのかがわかりにくくなります。このような理由から大きなプログラムでグローバル変数を使うことは bad practice とされていますので使用は極力避けたいものです。

`nonlocal` 文を使った再帰関数

Python の nonlocal 文の詳細については公式ドキュメントおよびPEP3104に書かれています。

nonlocal 文は、指定された変数を nonlocal があるスコープから外側に向かって、グローバルスコープにたどり着くまで探します（グローバルスコープそのものは含みません）。

def nonlocal_example():
    foo1 = "123"
    foo3 = "789"
    foo4 = "def"
    def my_inner_func():
        foo2 = "456"
        foo3 = "abc"
        nonlocal foo4  # 再帰関数の場合はこのfoo4のような動きになる。
        def my_inner_func_2():
            nonlocal foo1
            nonlocal foo2
            nonlocal foo3
            nonlocal foo4
            foo1 = foo1 + "000"
            foo2 = foo2 + "000"
            foo3 = foo3 + "000"
            foo4 = foo4 + "000"
            print(foo1)
            print(foo2)
            print(foo3)
            print(foo4)
        my_inner_func_2()
    my_inner_func()

nonlocal_example()
# 123000
# 456000
# abc000
# def000

この nonlocal 文を使ったピーマンの袋詰めのための再帰関数は以下のようになります。

def recursive_search_nonlocal_outer(item_list):
    overall_closest = sum(item_list)
    overall_closest_mask_bit_string = "1" * len(item_list)
    def recursive_search_nonlocal_inner(
        item_list,
        temp_sum=0,
        item_index=0,
        current_mask_bit_string="",
    ):
        nonlocal overall_closest
        nonlocal overall_closest_mask_bit_string
        if overall_closest == 150:
            pass
        elif item_index == len(item_list):
            # ...中略...
        elif item_index < len(item_list):
            # ...中略...
            elif temp_sum < 150:
                recursive_search_nonlocal_inner(item_list, temp_sum, item_index + 1, current_mask_bit_string+"0")
                recursive_search_nonlocal_inner(item_list, temp_sum+item_list[item_index], item_index + 1, current_mask_bit_string+"1")
            else:
                raise Warning("You've missed something!")
        else:
            raise Warning("You've missed something!")
        while len(overall_closest_mask_bit_string) < len(item_list):
            overall_closest_mask_bit_string += "0"
        return overall_closest, overall_closest_mask_bit_string
    return recursive_search_nonlocal_inner(item_list)

最初の例ではグローバル変数として宣言した overall_closest と overall_closest_mask_bit_string を、ここでは recursive_search_nonlocal_outer という関数の中で宣言し、nonlocal を使って recursive_search_nonlocal_inner の中からそれらを参照しています。そして最後に recursive_search_nonlocal_outerの返り値が recursive_search_nonlocal_inner の返り値となるよう recursive_search_nonlocal_inner を最後の return の中で呼び出しています。

この関数を使ってみましょう。

recursive_search_nonlocal_outer(bell_peppers)
# (150, '000010001110')

recursive_search_nonlocal_outer(bell_peppers_2)
# (160, '11110')

どちらも正しい結果が得られましたね。この書き方によって関数を純粋関数として書くことができているので、関数としても使いやすくなりました。

このように nonlocal を使うことでグローバル変数を使うことなく再帰処理を行うことができます。

補足

せっかくなので150g以外の重さでも袋詰めを行えるように、目標の重量を指定できるように関数を変えてみます。

def recursive_search_with_nonlocal_2(item_list, target_weight):
    overall_closest = sum(item_list)
    overall_closest_mask_bit_string = "1" * len(item_list)
    def recursive_search_nonlocal_inner(
        item_list,
        temp_sum=0,
        item_index=0,
        current_mask_bit_string="",
    ):
        nonlocal overall_closest
        nonlocal overall_closest_mask_bit_string
        if overall_closest == target_weight:
            pass
        elif item_index == len(item_list):
            if temp_sum >= target_weight:
                if abs(temp_sum - target_weight) <= abs(overall_closest - target_weight):
                    overall_closest = temp_sum
                    overall_closest_mask_bit_string = current_mask_bit_string
                elif abs(temp_sum - target_weight) > abs(overall_closest - target_weight):
                    pass
                else:
                    raise Warning("You've missed something!")
            elif temp_sum < target_weight:
                pass
            else:
                raise Warning("You've missed something!")
        elif item_index < len(item_list):
            if temp_sum >= target_weight:
                if abs(temp_sum - target_weight) <= abs(overall_closest - target_weight):
                    overall_closest = temp_sum
                    overall_closest_mask_bit_string = current_mask_bit_string
                elif abs(temp_sum - target_weight) > abs(overall_closest - target_weight):
                    pass
                else:
                    raise Warning("You've missed something!")
            elif temp_sum < target_weight:
                recursive_search_nonlocal_inner(item_list, temp_sum, item_index + 1, current_mask_bit_string+"0")
                recursive_search_nonlocal_inner(item_list, temp_sum+item_list[item_index], item_index + 1, current_mask_bit_string+"1")
            else:
                raise Warning("You've missed something!")
        else:
            raise Warning("You've missed something!")
        while len(overall_closest_mask_bit_string) < len(item_list):
            overall_closest_mask_bit_string += "0"
        return overall_closest, overall_closest_mask_bit_string
    return recursive_search_nonlocal_inner(item_list)

180gの袋詰めを行ってみます。

recursive_search_with_nonlocal_2(bell_peppers, 180)
# (180, '000000111001')

このピーマンの袋詰めの例は2017年に放送された「大人のピタゴラスイッチピーマンとハトと数学」に出てきたものです。なぜかとても印象に残っていたのでここでも例として使わせていただきました。 ↩
枝刈り全探索のコードは増井敏克さんによる「Pythonではじめるアルゴリズム入門」の p.162 の問題2の解答（p.267）を参考にさせていただいています。 ↩