室村日記

プログラミング初心者のメモ書きです

Pythonでオセロをつくってみる

天啓により,Pythonでオセロを作ることを思い立ちました.
まずは簡単なボードの実装から始めて,候補手(合法手)を出してくれる機能を追加したり,UIをちゃんと(クリックで駒が置けるなど)していきたいと考えています.
将来的には,自分で学習させたComとの対戦なども……

ちなみにプログラミングもアルゴリズムもかなりの初心者のため,間違っているところやかなり危ないところ,多々あるかと思います.ご指摘いただけると幸いです.

早速ですが,以下コンテンツ.
逐次追加予定です.かなり長くなる予定です.

はじめに

動機

Pythonの勉強として競技プログラミングも始めたのですが,そろそろプロダクトを作ってみたくなったためオセロに挑戦することにしました.
あとは簡単な機械学習を試してみたいという欲望もあります.

縛り

Pythonそのものについてググってもよいとする.
・勉強にならないので,オセロの実装についてはあまりググらないこととする.


ボードの実装

オセロボードをどう表現するか

まず駒をどう表現するか考えました.
オセロに登場する駒は○と●の2つです.
また1つのマスに注目すると, 駒が何も置かれていない/○が置かれている/●が置かれているの3通りあることがわかります.盤面の出力の都合上,何も置かれていない状態をとりあえず〼で表すことにします.
これらをそれぞれ数字の1,2,3で表すことにしました.つまり,対応関係は{〼(何も置かれていない):0, ○:1, ●:2}となります.

次に,ボード全体をどう表現するか考えました.
オセロは8×8のボードゲームです.よって最初はそのまま8×8の2次元配列を用いようと思っていました.
が,ここで1つ疑問が発生.オセロなので,駒を置いたときに周りの駒をひっくり返せるか探索する必要があります.このときボードの端が絡んでくると,少し判定が面倒になることが予想されます.(具体的には,端より向こう側は0/1/2によって表現されていないので,探索の中に端を探索しているという条件を書かなくてはいけなくなる)
そこで,10×10の2次元配列を用い,外周1マス分はボードのエッジとして■で表現することにしました.この数字には9を用いることにします.
よって,現在の対応関係は{0:"〼", 1:"○", 2:"●", 9:"■"}となります.
オセロボードのイメージはこんな感じ
f:id:muromura:20170724233300p:plain

あとは,これらをどう実装するかです.
これからどう進むか全くわかりませんが,とりあえず練習ついでに,クラスとしてオセロボードを実装することにしました.
新規ゲームのたびに,オセロボードクラスからインスタンスをつくるイメージです.
あとは,オセロの盤面を出力するための関数を別に定義しておきます.
これはとりあえず,2次元リストを1行ずつ出力するだけのものです.

ここまでのコードは以下です.

def otlprint(board):  #盤面を出力する関数
    for i in range(10):
            print(board[i])    

#Othello Class
class OthelloBoard:
    def __init__(self):
        self.board = [[0 if 0<i<9 else 9 for i in range(10)] if 0<j<9 else [9 for i in range(10)] for j in range(10)]  #ボード準備
        self.board[4][4], self.board[4][5], self.board[5][4], self.board[5][5] = [1,2,2,1]  #初期配置
        print("初期配置")
        otlprint(self.board)

出力部分の工夫

どうせなら出力するときには0/1/2/9のわかりにくい表示から,〼/○/●/■のわかりやすい,それっぽい表示にしたいところです.
これは出力関数をちょっといじることで簡単に実装できました.

def otlprint(board):  #数字で表現された盤面を●や◯に変換する関数
    convert_dict={0:"〼", 1:"○", 2:"●", 9:"■"}
    converted_list = [[convert_dict[board[j][i]] for i in range(10)] for j in range(10)]
    for i in range(10):
            print("".join(converted_list[i]) )   

わーい それっぽーい
f:id:muromura:20170724234334p:plain

ひっくり返す機能の実装

次に,オセロボードクラスのメソッドとして,1.指し手の入力を受け付けて盤面を変化させる(オセロのルールに則って駒をひっくり返す)機能と,2.現在の盤面を出力する機能をつくります.

オセロはタテ・ヨコ・ナナメにひっくり返すことができるので,近傍8マスの延長線上を探索していけばいいということになります.
ひっくり返せるかどうかの判定は,以下のアルゴリズムに従えばできそうです.

for 探索方向 ∈ 8近傍 do
    探索方向に1マス進む
        if 相手の色以外 then
            その方向の探索終了
        else:
            while 現在のマスに相手の色の駒が置かれている
                現在のマス目を記憶する
                探索方向に1マス進む
                    if 現在のマスに自分の色の駒が置かれている:
                    for マス目 ∈ 履歴 do
                        マス目の駒を自分の色に変える

このアルゴリズムの場合,ボードの端を9として表現しておいたおかげで,端に到達したらwhile文を自動的に終了させることができます.良い方法なのかどうかはわかりませんが,動くことには動きます.

あとは数点考えておきたいポイントがありました.
探索方向については8通りしかないので,インスタンス変数かクラス変数で定義しておくと良さそうです.
また将来,対局を振り返る機能をつくりたいので,一手ごとに盤面を逐次格納するためのインスタンス変数も確保しておきたいところです.

これらを用いてアップデートしたオセロボードクラスは以下のようになりました.

#オセロ(othello)を組んでみる
def otlprint(board):  #数字で表現された盤面を●や◯に変換する関数
    convert_dict={0:"〼", 1:"○", 2:"●", 9:"■"}
    converted_list = [[convert_dict[board[j][i]] for i in range(10)] for j in range(10)]
    for i in range(10):
            print("".join(converted_list[i]) )                
                
    
            
#Othello Class
class OthelloBoard:
    def __init__(self):
        self.board = [[0 if 0<i<9 else 9 for i in range(10)] if 0<j<9 else [9 for i in range(10)] for j in range(10)]  #ボード準備
        self.board[4][4], self.board[4][5], self.board[5][4], self.board[5][5] = [1,2,2,1]  #初期配置
        self.direction = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]  #周辺8マスへの方向
        self.hist = []  #履歴メモ用
        print("初期配置")  #インスタンス呼び出し時に初期配置を出力
        otlprint(self.board)
        
    def put(self, teban, pos):  #打ち手を入力して盤面を更新する
        self.board[pos[0]][pos[1]] = teban
        for dx,dy in self.direction:  #8近傍から伸びる直線のうち,どれを探索しているか
            x = pos[0]+dx
            y = pos[1]+dy
            if( self.board[x][y]!=3-teban ): #相手の色以外ならその方向の探索終了
                continue
            else:
                tmp=[] #探索したマスのメモ
                while ( self.board[x][y]==3-teban ): #相手の色である限り探索方向に進む
                    tmp.append([x,y])
                    x+=dx
                    y+=dy
                if ( self.board[x][y]==teban ):  #挟まれていたら,手番の色にひっくり返す
                    for x,y in tmp:
                        self.board[x][y]=teban
        self.hist.append(self.board)
        
    def out(self): #現在の局面を表示する
        print("\n",len(self.hist),"手目")
        otlprint(self.board)


動作チェックは以下.

board = OthelloBoard()

board.put(1,[5,3])
board.out()
board.put(2,[6,3])
board.out()
board.put(1,[6,4])
board.out()
board.put(2,[6,5])
board.out()

f:id:muromura:20170724230918p:plain
いまのところちゃんと動いているようです!

Python3でグラフと深さ優先探索・幅優先探索の実装

競技プログラミングのある問題に取り組んでいるとき,解き方はわかったのに,pythonでのグラフとその探索の実装の仕方が分からずに詰んで悲しい思いをしたので,まとめました.

1 グラフの実装

ノードとエッジに関する情報は,競技プログラミングでよくあるように以下の形式で与えられるとします.
ノード(頂点)数はNで,a_i番目のノードとb_i番目のノードをi番目のエッジが結んでいます.

N
a1 b1
・
・
・
aN bN

今回は例としてノード数7,エッジ数6のグラフを考えてみます.

7
3 6
1 2
3 1
7 4
5 7
1 4

図にするとこんな感じ.
f:id:muromura:20170716021330p:plain

このグラフの情報を以下の形式で持っているとします.

n=7  #ノード数
p = [[3,6], [1,2], [3, 1], [7,4], [5,7], [1,4]] #エッジ

今回の実装は,上の形式でデータが与えられるのであれば,無向グラフにも有向グラフにも使えます・


さて,グラフの実装の仕方は隣接行列と隣接リストの2通りあります.
どちらも一長一短ありますが,今回はエッジ数がノード数の2乗に比して小さい場合に無駄が少ない隣接リストを使います.

#隣接行列に格納
m =[ [0]*n for i in range(n)]
for path in p:
    m[path[0]-1][path[1]-1] = 1
print(m) 

#隣接リスト
l = [[] for i in range(n)]
for pi in p:  #0-originedに注意
    l[pi[0]-1].append(pi[1]-1)
    l[pi[1]-1].append(pi[0]-1)
print(l)

ちなみに重みありのグラフの場合の隣接行列は

n=7  #ノード数
p = [[3,6,1], [1,2,2], [3, 1,3], [7,4,4], [5,7,5], [1,4,6]]

#隣接行列
mw =[ [0]*n for i in range(n)]
for path in p:
    mw[path[0]-1][path[1]-1] = path[2]
print(mw) 

探索

グラフの探索にはいくつかの方法がありますが,そのうち深さ優先探索幅優先探索を実装したものが以下となります.
ここでは頂点ナンバーを訪れた順に出力する関数を定義しています.

深さ優先探索

#深さ優先探索
def dfs(Graph, Start, Visited=None):
    if (Visited==None):  Visited = [] #開始点のときに探索済みリストをつくる
    Visited.append(Start)  #現在の頂点を探索済みリストに加える    
    print(Start, "\n", Visited)  #現在の頂点と探索済みリストを表示
    for Next in Graph[Start]:  #次に探索する頂点の候補
        if ( Next in Visited ):  continue  #訪問済みリストにある頂点は飛ばす
        dfs(Graph, Next, Visited)  #再帰

#頂点0(1)から探索
dfs(l, 0)

実行結果

0 
 [0]
1 
 [0, 1]
2 
 [0, 1, 2]
5 
 [0, 1, 2, 5]
3 
 [0, 1, 2, 5, 3]
6 
 [0, 1, 2, 5, 3, 6]
4 
 [0, 1, 2, 5, 3, 6, 4]

幅優先探索

#幅優先探索     
def bfs(Graph, Start):
    visited= {Start: None} #親子ノードを対にした訪問済みリスト
    unvisited = [Start]  #現在の頂点から見た未訪問リスト
    while unvisited: #未訪問リストにある点それぞれについて考える
        Now = unvisited[0]
        unvisited = unvisited[1:]
        print(Now, "\n", visited,"\n", unvisited)  #現在のノードと訪問済みリスト
        for Next in Graph[Now]:  #次に探索する頂点の候補
            if not(Next in visited):  
                unvisited.append(Next)  #新しい候補点をリストに追加
                visited[Next] = Now  #親子ノードを記入
    return visited

bfs(l,0)

出力結果

0 
 {0: None} 
 []
1 
 {0: None, 1: 0, 2: 0, 3: 0} 
 [2, 3]
2 
 {0: None, 1: 0, 2: 0, 3: 0} 
 [3]
3 
 {0: None, 1: 0, 2: 0, 3: 0, 5: 2} 
 [5]
5 
 {0: None, 1: 0, 2: 0, 3: 0, 5: 2, 6: 3} 
 [6]
6 
 {0: None, 1: 0, 2: 0, 3: 0, 5: 2, 6: 3} 
 []
4 
 {0: None, 1: 0, 2: 0, 3: 0, 5: 2, 6: 3, 4: 6} 
 []
Out[16]:
{0: None, 1: 0, 2: 0, 3: 0, 4: 6, 5: 2, 6: 3}

Pythonはzero based indexingなので,i番目の頂点がi-1として表されることに注意が必要です.

まとめ

とりあえず今は訪問順にそのまま出力しているだけで,ほとんど何もしていません.
自由に探索をができるようになるまでは,もう少し習熟が必要なようです.

ウソつき問題とGW法

たまに見るウソつき問題にGW法という名前の万能の解法があることを知ったので,納得できるまで考えてみました.

はじめに

ウソつき問題とは以下のようなタイプの問題です.
誰しも小学生の頃にクイズ本やテレビのクイズ番組などで見たことがあると思います.

A~Dの4人が以下のようにそれぞれ証言している.
ただし,各人は必ずしも本当のことを言っているとは限らない.
A「Dはウソつきだ」
B「Cはウソつきだ」
C「AかDのどちらかはウソつきだ」
D「AかCのどちらかはウソつきだ」

このとき,以下の選択肢の中で,確実に正しいものはどれか.
1 Aはウソつきでない
2 Bはウソつきでない
3 Cはウソつきだ
4 Dはウソつきでない
5 ウソつきは2人いる

GW法の概要

正式名称はGrands Wagons法というらしいです.
さて,この作戦はたったの2ステップで表せます.
1.特定の発言によって登場人物をウソつき/正直者にグループ分けする
2.その他の発言によって正解を見つける

GW法

上の例であげた問題を考えてみます.

0.前提
まず,4人の人間がいます.
f:id:muromura:20170714143025p:plain
誰かはわかりませんが,ウソつきがいるようです.
f:id:muromura:20170714143040p:plain
ここでは正直者を白い人間,ウソつきを黒い人間で表してみます.
(あくまで例,上の問題でBとDがウソつきだというわけではないので注意)


1.グループ分け
あるタイプの証言に注目し,ルールに沿って登場人物をグループ分けします.
注目する証言のタイプは,『〜は正直者/ウソつきだ』のように特定の人物がウソつきかどうか直接的に言及しているものです.
そのとき,以下のルールに沿ってグループ分けすることができます.

・A「Bはウソつき」 なら AとBは違うグループ
・A「Bは正直」 なら AとBは同じグループ

Aがウソつきかどうかも分からないのに,本当にグループ分け出来ているの?と思ったので詳しく見てみます.

Aが「Bはウソつき」と言っている
f:id:muromura:20170714142334p:plain
f:id:muromura:20170714142755p:plain

Aが「Bは正直者」と言っている
f:id:muromura:20170714142827p:plain
f:id:muromura:20170714143202p:plain

どの場合も,AとBが同じグループに属するかどうかについて,正しく判断できていることがわかりました.

上の問題では,他者に直接言及しているのはAとBです.
ルールを適用すると,AとDは違うグループである,BとCは違うグループである,の2つがわかります.
ここでAとBがそれぞれウソつきかどうかを考えると,以下の4パターンのグループ分けが考えられます.
f:id:muromura:20170714143551p:plain
f:id:muromura:20170714143612p:plain
f:id:muromura:20170714143603p:plain
f:id:muromura:20170714143607p:plain




2.正解を見つける
つぎに,残るCとDの発言に注目して正解を見つけたいと思います.

Cの発言に注目すると,「AかDのどちらかはウソつき」と言っており,Aの発言からこれは明らかに正しいです.
よってCは正直者となります.
グループ分けの中でCが正直者となっているのは①と④で,ひとまずこれらが候補となります.

つぎにDの発言に注目します.
Cが確実に正直者であることはわかっているので,Dがウソつきかどうかを考えてみます.
①の場合はAはウソつき,CとDが正直者で,Dの発言内容と合致します.
④の場合はAとCが正直者,Dがウソつきとなりますが,これもDの発言内容が嘘ということとなり合致します.

以上より①と④はどちらもあり得るので1つに絞れません.
f:id:muromura:20170714143551p:plain
f:id:muromura:20170714143607p:plain
ここから確実に言えるのは,「Bがウソつき」「Cは正直者」「正直者とウソつきは2人ずつ」くらいです.
選択肢をみると,5の「ウソつきは2人いる」が正しいことがわかりました.


まとめ

以上がGW法によるウソつき問題の解法になります.
ルールにより機械的に分類作業をすすめ,あとは組み合わせを考えるだけなので,慣れるとかなり高速で解くことができそうです.



余談

A「Aはウソつきだ」

のような,自分について言及するような証言は,ウソつき問題では一般的に含まれません.
これはウソつきのパラドックスだとかエピメニデスのパラドックスとか言われる,自己言及のパラドックスというものの一種になるため回答者に誤解を与えるからだと思われます.
[wiki:自己言及のパラドックス]

Python3で再帰関数

python3での再帰関数とメモ化についてまとめました.

はじめに

再帰関数とは.
定義の中に,自分自身を呼び出す(再帰)ようにして定義される関数のことです.
今回例にあげる再帰関数は,引数nが定数で明らかにn回以下のの繰り返しで書き換えることが可能なものばかりですが,再帰を用いて定義することにより簡単に記述することができます.

再帰関数はシンプルに実装すると,同じ計算を何回もすることが多いので,計算量の無駄が多くなります.
無駄を減らすためにいくつかの方策があるようなので,調べてまとめてみました.


例1:階乗

階乗とは,
 n! = n * (n-1) * \cdots *2 * 1
の計算のことです.階段のように一段ずつ変化する数をかけていくのでこう呼ばれています.
これを素直に実装すると,

 #階乗
def easyFact(n):
    if ( n==0 ): 
        return 1
    else: 
        return n*easyFact(n-1)

#結果
print([easyFact(i) for i in range(10)])

となります.


結果は

[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

例2:ユークリッドの互除法を用いた最大公約数

#最大公約数
def gcd(a,b):
    if ( b==0 ):
        return a
    else:
        return (gcd(b, a%b))

#結果
print(gcd(456,276))

結果は

12

本題:フィボナッチ数列

本題のフィボナッチ数列です.
フィボナッチ数列は,
1 1 2 3 5 8 13......
と,前2つの数を足していくことでつくられる数列です.少し前にダヴィンチ・コードなどで取り上げられて一躍有名になりました.


単純

#単純な再帰
def simFib(n):
    if ( n<=1 ):
        return 1
    else:
        return simFib(n-2) + simFib(n-1)

フィボナッチ数列のルールとして,初項は1,第2項は(0+1)で1が予め決まっています.
第3項以降は上であげた漸化式 a_{n+2} = a_{n+1}+a_nに沿って計算していきます.
この例ではnを更新するたびにわざわざ初項から計算しなおすことになり,実行速度が大変遅くなります.


末尾再帰

高速化には以下のような方針があります.

def endFib(n, a1 = 1, a2 = 0):
    if (n < 1): 
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)

直前の2つの値をa1,a2に記憶しておけば計算量が減るという考え方です.

繰り返し

def repFib(n):
    a1, a2 = 1, 0
    while n > 0:
        a1, a2 = a1 + a2, a1
        n -= 1
    return a1

末尾再帰は繰り返しに書き換えることができます.

行列

import numpy as np
def matFib(n):
    m = np.matrix('1 1 ; 1 0') ** n
    return m.item(0)

あくまでフィボナッチ数列に限った話ですが,この数列は行列をn乗した行列の要素として表現できます.
よって計算量はO(n)となります.

メモ化

本命です.
実はmemoFib()の動作はsimFib()と全く同じですが,メモ化関数memoize()を定義し,デコレータ表記を用いてメモ化しています.

def memoize(f): #メモ化関数
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def memFib(n):
    if ( n<=1 ):
        return 1
    else:
        return memFib(n-2) + memFib(n-1)

メモ化を用いることによって一度計算した値を記憶し,次にその値が欲しいときは,計算抜きにメモから呼び出せるようになります.
何回も同じ計算を実行するときなどに非常に早く計算できます.


実行時間の比較

お待ちかね,速度比較です.
フィボナッチ数列の第n項をFib(n)として,Fib(1)からFib(30)までを計算する時間の和を測りました.
いちいち書くのが煩雑だったので,計測過程を関数化しています.

import time
#計測用関数
def tc(func, n):
    s = time.time()
    a = [func(i) for i in range(n)]
    e = time.time() - s
    return  '{0:8.6f}'.format(e)+'秒'

#比較
print("単純__:", tc(simFib, 30))
print("末尾再帰:", tc(endFib, 30))
print("繰り返し:", tc(repFib, 30))
print("行列__:", tc(matFib, 30))
print("メモ化_:", tc(memFib, 30))


結果です.

単純__: 0.754400秒
末尾再帰: 0.000116秒
繰り返し: 0.000050秒
行列__: 0.002787秒
メモ化_: 0.000014

単純に書いた場合が圧倒的に遅いのに対し,他の場合ではかなりの高速化が行われています.
特に今回は
Fib(1)を計算⇨,Fib(2)を計算 ⇨……Fib(30)を計算
というように30回分いちいちフィボナッチ数列を計算しているので,メモ化によって大きな恩恵を受けていることがわかります.

Python3で組み合わせ計算を高速化

初めに

Pythonで組み合わせ計算 {}_n\mathrm{C}_rを計算しようとすると,少々問題が発生します.
nやrが小さいうちはいいんですが,これが大きくなってくると計算が非常に長くなってくるのです.
実務や研究では少々計算が遅くても別に問題はないと思うのですが,競技プログラミングだとそれが命取りになってくるんですね……

組み合わせ計算のための元(と逆元)のテーブルの計算

階乗をメモしておく

というわけで,計算が重いなら予め計算した結果をテーブルにしといちゃいましょうというテクニックがあるそうです.

さて
 {}_n\mathrm{C}_r = \frac{n!}{r!(n-r)!}
からわかるように,単純に考えれば元 x! 1 \le x \le N(Nは考えられる最大)で計算してリストに書き込んでおけばよいことになります.
よって

#元
N  = 10
g =  [math.factorial(i) for i in range(N) ]

のように求めておけば,あとで10!の値が欲しければg[10]を呼び出すことにより,O(1)で組み合わせ計算を行うことができます.

組み合わせ計算は

def combination(n,r):
    return int(g[n]/(g[r]*g[n-r]))

出力できる数値に最大値の制限がある場合(合同な整数として考える場合)

ここから先は競プロ特有の話になります
上のようにテーブルに記憶させた場合でも,nやrが大きくなってくると,そもそもの階乗の計算量が膨大になります.

ここで,出力に制限がある状態にはさらに高速にテーブルを作成することができるようです.
具体的には「出力は 10^9+7で割った余りとせよ」のような場合のことです.


 {}_n\mathrm{C}_r = \frac{n!}{r!(n-r)!}
について,元 x!と逆元 (x!)^{-1} 1 \le x \le N(Nは考えられる最大)で計算しておくことを考えます.

 10^9+7素数なので,フェルマーの小定理より
 x ≡ x^{10^9 + 7} \ \ (\mathrm{mod} \ 10^9 + 7)
両辺を x^2で割って
 x^{-1} ≡ x^{10^9 + 5} \ \ (\mathrm{mod} \ 10^9 + 7)
となっています.

元と逆元のテーブルは,以下のように作成し,

mod = 10**9+7  #出力の制限
N = 10**4 
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#以下のcom関数を用いて組み合わせを計算
def com(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

利用した定理などの実装と説明

二分累乗法

xをn乗したいとして,普通に計算するとn回累乗計算を行うことになるので,計算量は \mathrm{O}(n)になります.
これを高速にする二分累乗法というものがあり,Python3で以下のように実装できます.

# 二分累乗法
def power(x, n):
    y=1
    while( n>0 ):
        if ( n%2==0 ):
            x = x * x
            n = n/2
        else:
            y = y * x
            n = n-1
    return y

nを二進法展開するように2でどんどん割っています.
1.奇数のときは答えにxを掛けてnから1引く
2.偶数のときは答えはそのままにxを2乗してnを1/2にする
という操作を繰り返すのですが,最低でも2回に1回はnが1/2になるので計算量が  \mathrm{O}(\log_2 n)に減少するというわけです.

より数学的な(でも簡略な)説明は以下.

nを二進法で展開すると
 n  = 2^{s_1} + 2^{s_2} + \cdots + 2^{s_k}  ただし   0 \le s_1 < s_2 < \cdots < s_k
となる.これより x^n
 \begin{split} x^n  &= x^{2^{s_1} + 2^{s_2} + \cdots + 2^{s_k}} \\ &= x^{2^{s_1}}x^{2^{s_2}} \cdots x^{2^{s_k}} \end{split}
となる.このとき,各々の x^{2^{s_i}} x^{2^{s_{i-1}}}から順に計算していけるので,計算量は  \mathrm{O}(\log_2 n)になる.

フェルマーの小定理

wikipedia:フェルマーの小定理

p を素数とし、a を p の倍数でない整数(a と p は互いに素)とするときに、
 a^{p-1} ≡ 1 \ \ (\mathrm{mod} \ p)
すなわち、a の p − 1 乗を p で割った余りは 1 であるというもの

Python3で最小木問題とプリム法

最小木問題を解くアルゴリズムのうち,プリム法をPython3で実装したのでメモ.
プリム法の実装の理解だけでなく,matplotlibを使ったので良い練習になりました.

wikipedia:プリム法

import matplotlib.pyplot as plt
import random
import numpy as np
import math
import sys

#最小木問題をプリム法で解く

#点群をランダム発生
p = [[random.uniform(0,100), random.uniform(0,100)] for i in range(100)]

#空のリストを用意
e = []  #部分最小木
av = []  #部分最小木に含まれる頂点
pv = list(p)  #その他の頂点

#始点は任意
av.append(p[0])
pv.remove(p[0])

while 1:
    #比較のための初期値として十分大きい数を用意
    shortestlen = sys.float_info.max
    #部分最小木に追加する辺を為す2点の初期化
    kav = None  #部分最小木に含まれる頂点からの候補
    kpv = None  #その他の頂点からの候補
    for v1 in av:
        for v2 in pv:
            #重みの計算(ここでは距離)
            dist = math.sqrt(  (v1[0]-v2[0])**2 + ( v1[1]-v2[1] )**2 )
            if shortestlen > dist:
                shortestlen = dist
                #候補の更新
                kav = v1
                kpv = v2
    if shortestlen > 0:
        #部分最小木に追加
        e.append([kav , kpv])
    #確定した頂点を移す
    av.append(kpv)
    pv.remove(kpv)
    #全頂点に対する判定を終えたら終了
    if len(pv) == 0:
        break


# 最小木の描画
for l in e:
    l = np.array(l).T
    plt.plot(l[0], l[1], 'k-', lw=2)
plt.show()


結果は
f:id:muromura:20170701180710p:plain
となりました.

Python3で任意長のリストを取ろうと思ったらいつのまにかリスト内包表記を勉強していた

Python3で任意長のリストを宣言しておくのってどうしたらいいんだと思って調べていたら,いつの間にかリスト内包表記を勉強していました.

これを使うと,
1.とりあえずfor文で回した結果を片っ端からappendなどでリストに突っ込む
      ↓↓↓
2.要素1つ1つ判定しながらリストを加工(削除,要素の変更など)する
というような操作が1行で書けます.
正確に言うと,先に判定をして加工も済んだ要素で,リストをつくるという感じのようです.

任意長の配列

[0, 0, 0, 0, 0, 0, 0]

例えば 上のような長さ7のリストが欲しい時は,

[0]*7

と書けばよいですが,リスト内包表記という”[]の中にfor文を書く”やり方でも作ることができます.

 [0 for i in range(7)]

リスト内包表記

基本形

 [i for i in range(7)]

出力は

[0, 1, 2, 3, 4, 5, 6]

一番左のiがリストの要素となっています.
この場合では,右側のfor文でiが0から1つずつ増えていくと定義されていることになります.
よって例えば以下のように一番左のiを(i+1)に変えると,

 [(i+1) for i in range(7)]

出力は

[1, 2, 3, 4, 5, 6, 7]

となります.

if(後置)

要素をifで判定してリストに加えるかどうか決めることもできます.
この場合,for文のあとにif文を書きます.

 [i for i in range(7) if i<5]

5より小さいiのみが要素として追加され,

[0, 1, 2, 3, 4]

となります.

if else

if elseを使いたい時は最初にもってくる必要があります.

 [i if i<5 else 4 for i in range(7)]

iが5より小さい時はそのままiが要素となり,iが5以上のときは4が要素となります.

[0, 1, 2, 3, 4, 4, 4]

集計

リストなどで集計関数がそのまま使えます.例えば,

sum( [(i+1) for i in range(7)])

について,全要素の和となるので

28

が得られます.28は完全数ですね.

2重for

forを2回重ねることもできます.

[[i,j] for i in range(2) for j in range(5)]

この場合はiが2通り,jが5通り動くので,長さ10のリストができます.

[[0, 0],
 [0, 1],
 [0, 2],
 [0, 3],
 [0, 4],
 [1, 0],
 [1, 1],
 [1, 2],
 [1, 3],
 [1, 4]]