全探索をPythonで実装してみた

At Corderに向けたお勉強のアウトプットです。
Pythonで書いていますので、良ければご覧ください。

線形探索法

ここでは「与えられたデータの中から特定のものを探す」方法を扱います。
1重ループなので計算量はO(N)です。

flagを使った方法

リストの中から条件に合致するものがあるか、1つずつ確認していく手法です。
flagを最初Falseに設定しておいて、条件に合致するものがあればTrueに置き換え、ループをbreakします。
flagはbool変数なので、そのままif文の条件分岐に使えます。

N = 5
list = [5,2,4,7,9]
value = 4
flag = False

for i in range(N):
    if list[i] == value:
        flag = True
        break

if flag:
    print("Yes")
else:
    print("No")

条件を満たすものの場所を調べる

条件を満たすものがリストの何番目にあるか調べたいときは、if文の中でiを記憶させます。
下記ではidという変数を定義し、初期値としてiの取りえない値：-1を入れておきます。
線形探索が終わった時点でid==-1であった場合、条件を満たすものがなかったことが分かります。

N = 5
list = [5,2,4,7,9]
value = 4
id = -1

for i in range(N):
    if list[i] == value:
        id = i
        break

if id ==-1:
    print("nothing")
else:
    print(id)

最小値を求める

リストの最小値を求めたい場合は、if文の中で値を更新させます。
ここではmin_valueという値を定義し、min_valueよりも小さなlist[i]が来たら値を更新します。
min_valueの初期値はlist内の値が取りうる最大値を設定しておきます。

N = 5
list = [5,2,4,7,9]
min_value = 999999999999

for i in range(N):
    if list[i] < min_value:
        min_value = list[i]

print("最小値:",min_value)

ペアの全探索

次のような問題には2重ループが使えます。このときの計算量はO(N^2)です。
・最適なペアを探索する
・2組のデータからそれぞれ要素を抜き出す方法を最適化する

最適なペアを探索する

ここでは具体例として、2つのリストから取り出した値の和が最小値となる組み合わせを求めます。
出力するのは最小値をとるリストa,bの値と最小値です。
今回もmin_valueを更新する方式を用います。
尚、リストの長さはいずれもNであるとします。
ここでは扱いませんが、二分探索を使えば計算量をO(NlogN)に抑えて計算できます。

N=5
a = [5,2,4,7,9]
b = [4,7,2,10,11]
min_value = 999999999999

for i in range(N):
    for j in range(N):
        if a[i]+b[j] < min_value:
            min_value = a[i]+b[j]
            a_min = a[i]
            b_min = b[j]

print("最小値:{} (a = {}, b ={})".format(min_value, a_min, b_min))

組み合わせの全探索（bit全探索）

応用編です。理解が難しいかもしれませんが、雰囲気だけでもつかめたら幸いです。

2進法を使った組み合わせの考え方

例として、[a1,a2,a3]のうち和が10となる組み合わせの数を考えます。
まず、すべての組み合わせの数を考えると、選ぶ、選ばないの2択を3回繰り返すため、2**3=8となります。
このとき、選ぶを1、選ばないを0とすれば、すべての組み合わせは2進法で整理できます。
例えば、[a1,a3]のみを選ぶ場合、101なります。詳しくは次の表をご覧ください。

10進法表記	組み合わせ	2進法表記
0	[]	000
1	[a1]	100
2	[a2]	010
3	[a3]	001
4	[a1,a2]	110
5	[a1,a3]	101
6	[a2,a3]	011
7	[a1,a2,a3]	111

2進法を使った全探索とPythonコードの考え方

全探索ですので、すべての組み合わせの和を考えて、条件に合う（=10）組み合わせの数を数えます。
2進数は組み合わせ全パターンを考えるときに使います。
組み合わせの数を2進数に変換し、対応する桁が1の場合にその要素を足し合わせることで計算できます。
上記をコードで表現すると、(i >> j )&1です。
iを2進数表記でj桁右にシフトして下1桁が1なら1(True), 0なら0(False）を返します。
例えばi=5, j=1としたときを考えてみます。
5を2進数表記すると101で、この桁を1つずつ右にずらすと10になります。（1の位は切り捨て）
1桁目が0になるので、この操作ではsumに追加されないことになります。

pythonコード

上記をpythonコードにすると、下記のようになります。
リストaに対し、和が10となる組み合わせを出力しています。
このとき、[3,7]、[4,6]が条件を満たすので、2（通り）が出力されます。

a=[3,7,4,6]
n=len(a)
ans=0
for i in range(2**n):
    sum=0
    for j in range(n):
        if (i >> j)&1:
            sum += a[j]
    if sum==10:
        ans += 1
print(ans)

まとめ

全てのアルゴリズムの基本となる全探索をpythonで実装してみました。
やはりpythonは教本(C言語)と比べても短いコードで実装できて便利だと感じました。
これらをマスターしたらAt CoderのC問題くらいは解けるらしいです。
初心者の方の参考になれば幸いです。