2nd day.
Today's theme is Brute Force Search by using bit transformation.
Bit transformation is useful when we want to express all subsets of set.
Code is below.
- 全探索が有効打になるのは、そもそもの有り得る解の数が少ないとき。
- Bit全探索を使って、文字の組み合わせを全て試した。
- Bitに変えると、0か1かの文字列なので、今回の"(", ")"の2通りに上手く変換できた。
- これが3種類だと、3進法に変える。p種類なら、p進法を使えばよい。
- 今回の使用した、"checker"では、0を切ったらやめた。本当は上限を設けても良かった。
ここまで書いたが、何言ってるか伝わりにくく感じたので、イメージをお絵描きしたい。
- こちらを参照する。
- 実際に色分けをしつつ、書いた折れ線グラフがこちら。
from itertools import accumulate
N = int(input())
def checker(s):
#ビット風の数字列が条件を満たすか調べる
temp = 0
for i in range(N):
temp += s[i]
if temp >= 0:
#途中で0を割ってほしくない
pass
else:
return False
break
else:
if temp == 0:
#終わりが0なら、良い
return True
else:
return False
def transform_into_bit(x):
temp2 = [0] * N
for i in range(N):
if x%2 == 0:
element2 = 0
else:
element2 = 1
temp2[i] = 2 * element2 -1
x //= 2
#2で割って、1の位を見る
else:
return temp2
#リストで返す
all_answer =
#全ての答えを記憶
def bit_all_search():
for j in range(2**N):
temp3 = transform_into_bit(j)
if checker(temp3):
#良い答えを選別
answer =
for k in range(N):
#ここで文字列に変換する
if temp3[k] == 1:
answer.append("(")
else:
answer.append(")")
else:
print(*answer, temp3)
all_answer.append(list(accumulate(temp3)))
#後のために、累積和をとる
else:
pass
bit_all_search()
import matplotlib.pyplot as plt
x = [i for i in range(N+1)]
M = len(all_answer)
colorlist = []
#色分けするために、色のリストを作る
for a in range(11):
for b in range(11):
for c in range(11):
colorlist.append([a*0.1, b*0.1, c*0.1])
for i in range(M):
plt.plot(x, [0]+all_answer[i], marker = 'o', color=colorlist[20 * i] )
#全ての答えをグラフにする。
plt.show()
print("number of solution",M)
何通りかの式が気になるが、今は良いとする。
バイバイ！
