【Pythonで複数の数値から組み合わせを検索】
ツール公開とPythonでの実装方法を

記事イメージ


(最終更新日:

こんにちは、堺です。

ある数字があって、その数字が別の数字の明細のどれかを組み合わせ合計して出来ているはず。ただその組み合わせが分からない・・・って場面、財務分析などの仕事をしているとよくあります。

今回はこのように「複数の値からある合計に一致する組み合わせを探す」という問題をPythonで解決してみたいと思います。

※重要:今まさに組み合わせを調べたい人へ、こちらにWebツールを公開しています。入力数値の記録などは行っていないので安心してご利用ください。(ご利用及び結果の内容については、ご利用者様の責任のもとにお願いいたします。公開環境の問題でちょっと時間がかかります。)

Webツールの結果。566がどれを足し合わせればよいか?という問いに対して、4+325+159+78という解を得られます。
Webツールの結果

準備:リスト内のすべての組み合わせを抽出する

「複数の値からある合計に一致する組み合わせを探す」処理をPythonで作成していきます。今回はitertoolsモジュールを利用します。itertoolsは、様々なタスクのループを効率的に実行する標準モジュールです。

このモジュールに含まれるitertools.combinations関数は、iterableな要素(リスト)のn個の組み合わせを全て抽出し、タプル値で返してくれます。

言葉で書いても分かりにくいので、実際に実行してみます。

Python
import itertools

target_list = [632, 4, 367, 4335, 567, 325, 8, 159, 369, 35, 78, 33]

#itertools.combinationsを使って、リストから3個抜き出して出来る組み合わせをすべて列挙
#(第2引数が、抜き出す個数です。)
combis = itertools.combinations(target_list, 3)
for combi in combis:
    print(combi)

リストの値から3個抜き出してできる全ての組み合わせをタプル型で列挙してくれます。
リストの値から3個抜き出してできる全ての組み合わせをタプル型で列挙してくれます

このように、全ての組み合わせを得ることが出来ました。

この結果を利用して、得られたタプルの合計が目標数値にマッチするかどうかを逐次調べれば、組み合わせ検出が出来そうです。

完成:抜き出した組み合わせタプルの合計が目標数値にマッチしたら、結果として検出する

itertools.combinationsの結果をyieldする関数と、検証するコードを追加していきます。

Python
import itertools
from decimal import Decimal, Context

def yield_combinations(target_list):
    """
    引数の要素の組み合わせを全てyieldする
    Parameters
    ----------
    target_list : list
        元となる明細の数字リスト
        (上の例の [632, 4, 367, 4335, 567, 325, 8, 159, 369, 35, 78, 33]に相当)
    """
    #n=組み合わせ個数 1個から順番に抜き出す個数を上げていく。
    for n in range(len(target_list)):
        for conb in itertools.combinations(target_list, n + 1):
            yield list(conb) 

def get_all_combinations(target_list, target_number):
    """
    合計がtarget_numberに一致するtarget_listの要素の組み合わせを全て返す
    Parameters
    ----------
    target_list : list
        元となる明細の数字リスト
        (上の例の [632, 4, 367, 4335, 567, 325, 8, 159, 369, 35, 78, 33]に相当)
    target_number : decmal
        検索する目的となる、合計された数値(上の例の566に相当)
    """

    result = []

    for combi in yield_combinations(target_list):
        #明細から抜き出した組み合わせが目的数値に一致すれば、結果に追加
        if target_number == sum(combi):
            result.append(combi)

    #検出した組み合わせを全て返す
    return result

無事、566に一致する組み合わせを検出できました。
無事、566に一致する組み合わせを検出できました

注意点:何らかに実装する場合は、計算量にお気を付けください。

組み合わせを扱う計算の性質上、元の明細の数が増えるほど計算量は指数関数的に増えていきます。

何らかのアプリケーションなどに実装する場合は、計算回数や明細数に上限を設置して、巨大な計算が発生しない様にお気を付けください。

尚、私が公開しているツールでは、計算回数が一定以上に達した場合は処理を打ち切り、打ち切った事実とそこまでで得られた結果を表示する仕様としています。(この仕様実現のため、yield_combinations関数はyieldで結果を返す形式にしています。)

(ちなみに①)この例のような事務タスク処理は、デスクトップ上に実行環境を作ると便利

Pythonはこういった計算や大量ファイル処理などに便利で、事務効率化の強力なツールとなります。

Windowsでインストール不要な実行環境を作成するための過去記事がありますので、ぜひ併せてご参照ください。

関連記事:【Windowsですぐ始めるPython】Pythonで事務作業の効率化を体験してみよう

(ちなみに②)上でリンクしたWebツールはDjango+herokuでデプロイしました

PythonベースということもありDjango(PythonベースのWebアプリフレームワーク)で組み立てました。

herokuへのアップロードも相性が良く、開発体験としては上々でした。

参考リンク

python.org:itertools --- 効率的なループ実行のためのイテレータ生成関数

記事筆者へのお問い合わせ、仕事のご依頼

当社では、IT活用をはじめ、業務効率化やM&A、管理会計など幅広い分野でコンサルティング事業・IT開発事業を行っております。

この記事をご覧になり、もし相談してみたい点などがあれば、ぜひ問い合わせフォームまでご連絡ください。

皆様のご投稿をお待ちしております。

記事筆者へ問い合わせする

※ご相談は無料でお受けいたします。
IT活用経営を実現する - 堺財経電算合同会社