控え目な参加者
あなたは婚活に励んでいます。相手に望む年収は800万円以上です。婚活パーティーに出席したいですが、参加者の少なくとも1人は年収800万円以上でないと出席する意味はないと考えています。参加者とその年収のリストが与えられた時、出席する意味があるかどうかを答えない。
論理記号
参加者の集合を$M$、その年収を$Y$万円とします。上の条件は論理記号を用いて、
\exists M[Y\geq800]
と表せます。$\exists$は、「ある～が存在する」という意味です。要は**「一人でも年収800万以上がいれば即OK」**ということです。
プログラム例
def main1(M):
for Y in M:
if Y >= 800:
return "出席"
return "出席しない"
print(main1([800,900,1000,1100]))#出席
print(main1([500,600,700,800]))#出席
print(main1([400,500,600,700]))#出席しない
参加者を順に見ていき、800万円の人が見つかったらそこで探索を打ち切ればよいです。1人いれば後は何人いようが同じことです。
強欲な参加者
婚活パーティーの経験を何度も積んだあなたは段々強気になってきました。参加者の全員が年収800万円以上でなければ出席する意味はないと考えるようになりました。
論理記号
今回の場合は、
\forall M[Y\geq800]
と表せます。$\forall$は「あらゆる～について」という意味です。しかし、これをそのままプログラムに実装しようとすると少し面倒くさいので、ちょっとした論理変換を行います。上の命題は、
\lnot(\lnot \forall M[Y\geq800])
と同値です。$\lnot$は否定を表します。二択問題の場合、「『Aではない』ではない」は「Aである」と同値です。$\lnot$は$\forall$と$\exists$を入れ替えて右にずらすことができるという性質を利用すれば、
\displaylines{
\lnot(\lnot \forall M[Y\geq800])\\
\Leftrightarrow \lnot(\exists M\lnot[Y\geq800])\\
\Leftrightarrow \lnot(\exists M[Y<800])}
という変換が成り立ちます。要は**「一人でも年収800未満がいれば即アウト」**ということです。
プログラム例
def main2(M):
for Y in M:
if Y < 800 :
return "出席しない"
return "出席"
print(main2([800,900,1000,1100]))#出席
print(main2([500,600,700,800]))#出席しない
print(main2([400,500,600,700]))#出席しない
出席の判断も厳しくなっています。
やる気のない企画者
婚活パーティーに出席しすぎたあなたはいつの間にか企画する側に回っていました。出席者の要望に応えるために、複数のグループを手配することにしました。しかしあなたはやる気がないので、年収800万円以上の参加者が少なくとも1人いるグループが少なくとも1つあればいいだろうと考えました。最悪、全体でたった1人でもいいのです！ なんというやる気のない企画者でしょう。出席者はたまったものではありません。
グループの集合を$G$とすると、
\exists G \exists M[Y\geq800]
となります。この実装は簡単で、「一人でも年収800万以上がいればいい」というのは変わりません。
def main3(G):
for M in G:
for Y in M:
if Y >= 800:
return "合格"
return "不合格"
print(main3([[400,500,600,700],[500,600,700,800]]))#合格
print(main3([[400,500,600,800],[500,600,700,800]]))#合格
print(main3([[300,400,500,600],[800,900,1000,1100]]))#合格
print(main3([[800,900,1000,1100],[900,1000,1100,1200]]))#合格
完璧な企画者
あまりのテキトーさにクレームを受けたあなたは今度は完璧なラインナップを用意しようと思いました。すべてのグループのすべての参加者が年収800万円以上というものです。
\displaylines{
\forall G \forall M[Y \geq 800]\\
\Leftrightarrow \lnot(\lnot \forall G \forall M[Y \geq 800])\\
\Leftrightarrow \lnot(\exists G \lnot(\forall M[Y \geq 800]))\\
\Leftrightarrow \lnot(\exists G \exists M[Y < 800])\\}
全体の中で一人でも年収800未満がいれば即アウトです。実装は同様に簡単に行えます。
def main4(G):
for M in G:
for Y in M:
if Y < 800:
return "不合格"
return "合格"
print(main4([[400,500,600,700],[500,600,700,800]]))#不合格
print(main4([[400,500,600,800],[500,600,700,800]]))#不合格
print(main4([[300,400,500,600],[800,900,1000,1100]]))#不合格
print(main4([[800,900,1000,1100],[900,1000,1100,1200]]))#合格
現実的な企画者その1
完璧なラインナップは好評でしたが、人を集めるのが大変すぎてすぐに限界が来ました。今度はこのようなプランを考えました。
「メンバー全員が年収800万以上であるようなドリームチームがグループの中に少なくとも1つは存在する」
\displaylines{
\exists G \forall M[Y \geq 800]\\
\Leftrightarrow \exists G \lnot(\lnot \forall M[Y \geq 800])\\
\Leftrightarrow \exists G \lnot(\exists M[Y < 800])\\}
これの実装は、今までのように1つのループ内で済ませることは難しいですが、関数を分割することでシンプルに実装できます。
def main5(M):
for Y in M:
if Y < 800:
return False
return True
def main6(G):
for M in G:
if main5(M):
return "合格"
return "不合格"
print(main6([[400,500,600,700],[500,600,700,800]]))#不合格
print(main6([[400,500,600,800],[500,600,700,800]]))#不合格
print(main6([[300,400,500,600],[800,900,1000,1100]]))#合格
print(main6([[800,900,1000,1100],[900,1000,1100,1200]]))#合格
現実的な企画者その2
このドリームチームプランですが、ババを引かされた出席者から当然の如くクレームが入るようになりました。そこであなたは次のプランを考えました。
「各チームに年収800万以上が少なくとも1人いることは保証する」
\displaylines{
\forall G \exists M[Y \geq 800]\\
\Leftrightarrow \lnot ( \lnot \forall G \exists M[Y \geq 800])\\
\Leftrightarrow \lnot (\exists G \lnot(\exists M[Y \geq 800]))\\}
def main7(M):
for Y in M:
if Y >= 800:
return False
return True
def main8(G):
for M in G:
if main7(M):
return "不合格"
return "合格"
print(main8([[400,500,600,700],[500,600,700,800]]))#不合格
print(main8([[400,500,600,800],[500,600,700,800]]))#合格
print(main8([[300,400,500,600],[800,900,1000,1100]]))#不合格
print(main8([[800,900,1000,1100],[900,1000,1100,1200]]))#合格
これでようやく安定した運営ができるようになったのでした。めでたしめでたし。
おまけ
後者2つの場合を1つの関数内で完結させる場合は、フラッグ用のbool変数を別に用意する必要があります。
\displaylines{
\exists G \forall M[Y \geq 800]\\
\Leftrightarrow \exists G \lnot(\lnot \forall M[Y \geq 800])\\
\Leftrightarrow \exists G \lnot(\exists M[Y < 800])\\}
def main9(G):
for M in G:
fail_at_least = 0
for Y in M:
if Y < 800:
fail_at_least = 1
if not fail_at_least:
return "合格"
return "不合格"
\displaylines{
\forall G \exists M[Y \geq 800]\\
\Leftrightarrow \lnot ( \lnot \forall G \exists M[Y \geq 800])\\
\Leftrightarrow \lnot (\exists G \lnot ( \exists M[Y \geq 800]))\\}
def main10(G):
for M in G:
success_at_least = 0
for Y in M:
if Y >= 800:
success_at_least = 1
if not success_at_least:
return "不合格"
return "合格"
フラグの条件が混乱しやすいので、個人的には、名前が長くなってもfail_at_least（少なくとも1回は失敗）等の変数名をつけるようにしています。