Kei Minagawa's Blog

皆川圭(@keimina)のブログ、Pythonで試したことを書いていきます

if文を自動生成する方法


if文を自動生成する方法について記載します。


1 したいこと



以下のような表があったとき、入力 (a, b) を f(a, b) に変換する関数を自動で作成したいと思います。


a b f(a,b)
0 0 1
0 1 0
1 0 1
1 1 0


表1.


この関数を手動でプログラムすると以下のようになるかと思います。


コード:


def f(a, b):
if a==0 and b==0:
ret = 1
if a==0 and b==1:
ret = 0
if a==1 and b==0:
ret = 0
if a==1 and b==1:
ret = 1
return ret


上記の関数の出力が表1.の出力と同じになるか確認します。


コード:


from itertools import product
for x in product([0, 1], [0, 1]):
line = map(str, x + (f(*x),))
print("|".join(line))
'''
コメント:
itertools.product はドット積のパターンを生成するのに使用しています。
for文を入れ子にしなくて良くなるので便利です。'''


出力:


0|0|1
0|1|0
1|0|0
1|1|1


したいことをまとめると、、、


上記の表1.のような、入力と出力の関係を定義した表が与えられたとき、上記「def f(…):」の中でプログラムしたようなif文を自動生成生成したいということです。


2 解決策 (1)



解決策 (1) では if文を自動生成するプログラムを自作します。以下のように実装しました。


コード:


import pandas as pd

# 入力となる表を DataFrame として作成する
df = pd.DataFrame(
[[0, 0, 1],
[0, 1, 0],
[1, 0, 0],
[1, 1, 1]],
columns=['a', 'b', 'ret']
)

# 評価を入力とし用いて、関数fを定義するための文字列を作成する
arg_t = ",".join(df.columns[:-1])
if_t = ""
for l in df.values:
s = " and ".join("%s==%d"%(col, i) for col, i in zip(df.columns[:-1], l[:-1]))
if_t += " if %s:\n"%s
if_t += " ret = %d\n"%l[-1]


f_t = "def f({}):\n"\
"{}"\
" return ret".format(arg_t, if_t)

# 上で定義した文字列をインタプリンタで評価し、関数fを上書きする
exec(f_t)

# 関数fが期待通りの動作になっているか確認する
from itertools import product
for x in product([0, 1], [0, 1]):
line = map(str, x + (f(*x),))
print("|".join(line))


出力:


0|0|1
0|1|0
1|0|0
1|1|1


if文をテキストとして書いてそれを exec関数で評価して、関数を定義しています。その関数を使用して表と同じ出力を出力しています。


※exec関数は、文字列をインタプリンタの入力として評価します。予期しないバグの温床になるので使用しないようにしましょう。また、任意のコードを実行可能なので実行するのはセキュリティ上の危険が伴います。ソースコードをよく理解した上で使用しましょう。

念のため生成した関数を表示してみます.


コード:


print('====================作成した関数の表示====================')
print(f_t)


出力:


====================作成した関数の表示====================
def f(a,b):
if a==0 and b==0:
ret = 1
if a==0 and b==1:
ret = 0
if a==1 and b==0:
ret = 0
if a==1 and b==1:
ret = 1
return ret


問題なく自動生成されていることがわかります。


3 解決策 (2)



解決策としては 解決策 (1) でも問題ないのですが、もう少しスマートな方法はないでしょうか。調べたところ sympy.SOPform 関数このような問題を解決するのにうってつけな関数でした。sympy.SOPform 関数を使用すると、表1.のような表を与えると、それに紐づく論理式を組み立ててくれます。さらに、冗長な論理式であった場合は冗長でない論理式にしてくれます。


コード:


import pandas as pd
from sympy import symbols
from sympy.logic import SOPform

# 入力となる表を DataFrame として作成する
df = pd.DataFrame(
[[0, 0, 1],
[0, 1, 0],
[1, 0, 0],
[1, 1, 1]],
columns=['a', 'b', 'ret']
)

ss = symbols(" ".join(df.columns[:-1]))
idx = df.iloc[:, -1]==1

if any(idx):
variables = ss
minterms = df[idx].values[:,:-1].tolist()
g = SOPform(variables, minterms)# 出力が 1 になるパターンだけを第二引数に設定する


# 評価を入力とし用いて、関数fを定義するための文字列を作成する
arg_t = ",".join(df.columns[:-1])
f_t = "def f({0}):\n"\
" args_bak = {0}\n"\
" {0} = symbols('{0}')\n"\
" expr = {1}\n"\
" return int(bool(expr.subs(dict(zip([{0}], args_bak)))))".format(arg_t, str(g))

exec(f_t)

# 関数fが期待通りの動作になっているか確認する
for line in df.values.tolist():
line = line[:-1] + [f(*line[:-1])]
print("|".join(str(i) for i in line))


出力:


0|0|1
0|1|0
1|0|0
1|1|1


作成した関数も見てみます。


コード:


print(f_t)


出力:


def f(a,b):
args_bak = a,b
a,b = symbols('a,b')
expr = (a & b) | (~a & ~b)
return int(bool(expr.subs(dict(zip([a,b], args_bak)))))


「(a & b) | (~a & ~b)」が sympy.SOPform 関数で作成した論理式です。自動で論理式を作成してくれて大変便利です。


次は、もっと大きい表で試してみます。まず、先ほどより大きめの表を作成します。


コード:


import numpy as np
from itertools import product

np.random.seed(1)
ret = np.random.choice([0, 1], 16)
columns = ['a', 'b', 'c', 'd']
df = pd.DataFrame(list(product([0,1], [0,1], [0,1], [0,1])), columns=columns)
df['ret'] = ret
print(df)


出力:


a b c d ret
0 0 0 0 0 1
1 0 0 0 1 1
2 0 0 1 0 0
3 0 0 1 1 0
4 0 1 0 0 1
5 0 1 0 1 1
6 0 1 1 0 1
7 0 1 1 1 1
8 1 0 0 0 1
9 1 0 0 1 0
10 1 0 1 0 0
11 1 0 1 1 1
12 1 1 0 0 0
13 1 1 0 1 1
14 1 1 1 0 1
15 1 1 1 1 0


この表に対して、 前の手順と同じことをします。


コード:


from sympy import symbols
from sympy.logic import SOPform

ss = symbols(" ".join(df.columns[:-1]))
idx = df.iloc[:, -1]==1

if any(idx):
variables = ss
minterms = df[idx].values[:,:-1].tolist()
g = SOPform(variables, minterms)

# 評価を入力とし用いて、関数fを定義するための文字列を作成する
arg_t = ",".join(df.columns[:-1])
f_t = "def f({0}):\n"\
" args_bak = {0}\n"\
" {0} = symbols('{0}')\n"\
" expr = {1}\n"\
" return int(bool(expr.subs(dict(zip([{0}], args_bak)))))".format(arg_t, str(g))

exec(f_t)

print('========関数fが期待通りの動作になっているか確認する========')
# 関数fが期待通りの動作になっているか確認する
lst = []
for line in df.values.tolist():
line = line[:-1] + [f(*line[:-1])]
print("|".join(str(i) for i in line))
lst.append(line)
print('===================df と lst を比較する====================')
print('df と lst の', '比較OK' if df.values.tolist() == lst else '比較NG')
print('====================作成した関数の表示====================')
print(f_t)


出力:


========関数fが期待通りの動作になっているか確認する========
0|0|0|0|1
0|0|0|1|1
0|0|1|0|0
0|0|1|1|0
0|1|0|0|1
0|1|0|1|1
0|1|1|0|1
0|1|1|1|1
1|0|0|0|1
1|0|0|1|0
1|0|1|0|0
1|0|1|1|1
1|1|0|0|0
1|1|0|1|1
1|1|1|0|1
1|1|1|1|0
===================df と lst を比較する====================
df と lst の 比較OK
====================作成した関数の表示====================
def f(a,b,c,d):
args_bak = a,b,c,d
a,b,c,d = symbols('a,b,c,d')
expr = (b & ~a) | (~a & ~c) | (b & c & ~d) | (b & d & ~c) | (a & c & d & ~b) | (~b & ~c & ~d)
return int(bool(expr.subs(dict(zip([a,b,c,d], args_bak)))))


作成した関数の出力と、表で定義した関数の出力が同じであることを確認し、問題なく、動作していることがわかります。


4 sympy.SOPform 関数について理解を深める



sympy.SOPform 関数を使用して自動で求まった論理式ですが、以下の sympy.logic.boolalg.to_dnf 関数を通しても同じなります。


コード:


from sympy.logic.boolalg import to_dnf
print(to_dnf(expr, simplify=True))


出力:


(b & ~a) | (~a & ~c) | (b & c & ~d) | (b & d & ~c) | (a & c & d & ~b) | (~b & ~c & ~d)


to_dnf関数とはなんでしょうか?関数のドキュメントをみてみます。


sympy.logic.boolalg.to_dnf(expr, simplify=False)

Convert a propositional logical sentence s to disjunctive normal
form. That is, of the form ((A & ~B & …) | (B & C & …) | …) If
simplify is True, the expr is evaluated to its simplest DNF form using
the Quine-McCluskey algorithm.


引数 simplify=True のとき Quine-McCluskey アルゴリズムで最も単純なDNF形式に変換されるとあります。参考文献No4. によると Quine–McCluskey アルゴリズムはブール関数を最小化するために使用されるアルゴリズムとのことです。また、参考文献No2. No3. から DNF とは論理式を表現する時に使える演算子を制限した論理式のフォーマットのようなものだと解釈しました。このような、分野をブール関数の簡単化(参考文献No6.)というようです。


まとめると、解決策 (2) では sympy.SOPform 関数を使用して、真理値表からブール関数を自動的に構築するだけでなく、そのブール関数の簡単化を行ったということになります。


5 参考文献



参考文献は以下の通りです。

No. タイトル URL 内容
1 Logic https://docs.sympy.org/latest/modules/logic.html sympy.SOPform関数について
2 連言標準形 https://ja.wikipedia.org/wiki/連言標準形 CNFについて
3 選言標準形 https://ja.wikipedia.org/wiki/選言標準形 DNFについて
4 Quine–McCluskey algorithm https://en.wikipedia.org/wiki/Quine–McCluskey_algorithm Quine–McCluskey algorithmについて
5 クワイン・マクラスキー法 https://ja.wikipedia.org/wiki/クワイン・マクラスキー法 クワイン・マクラスキー法について
6 ブール関数 https://ja.wikipedia.org/wiki/ブール関数 ブール関数について、簡単化について



以上です。