Python3 – 正規表現~貪欲と非貪欲

以下のようにタグで囲まれた文字からタグを取り出そうとすると、先頭の'<‘と最後尾の’>’に対して文字列全体がマッチしてしまう。

これは正規表現のマッチングができるだけ長い文字列でヒットさせようとする貪欲な(greedy)マッチングのため。

これを非貪欲(non-greeding)なマッチングにするためには**?とする。この場合、できるだけ短くマッチするようになり、個々のタグが分解される。

タグの間に1文字以上入っていることを意図して以下のようにしても、やはり貪欲にマッチする。

これを非貪欲にマッチさせようとすると、以下のように最初のタグのの'>'ではなく、その次の'>'にマッチする。最初のタグの'<'に対して、その後複数の文字を経て到達するのが2つ目のタグの'>'のため。

以下のように、意図する文字構成をできるだけ詳しく記述する方がよい。

 

Python3 – 文字列の判定~数値か文字か

文字列を構成する文字がすべて数値か、数値以外の文字かといった判定をするメソッド群。

isdecimal()
全ての文字が十進数字ならTrue
isdigit()
全ての文字が数字ならTrue
isnumeric()
全ての文字が数を表す文字ならTrue
isalpha()
全ての文字が数字以外の文字ならTrue
isalnum()
全ての文字が十進数字ならTrue

以下のコードで確認。

半角英字、半角数字の判定結果は想定通り。

半角記号は文字、数字、数を表す文字のいずれでもないと判定。

特殊数字は十進数字ではないが数字と判定。

漢数字は十進数字や数字ではないが、数を表す文字と判定。

全角の記号は文字、数字、数を表す文字のいずれでもないと判定。

 

Python – コマンドライン引数

コマンドライン引数の取得

以下のような仕様

  • sysパッケージをインポート
  • sys.argvに引数のリストが格納されている
  • 引数の1つ目(ゼロ番目)は常にコマンド自身

以下のスクリプトを実行してみる。

引数リストの先頭はコマンド自身(Windowsの\はエスケープされている)。

引数は入力したままの形。

引数がない場合の処理と、数値・文字別の処理を組み込んだ例。

実行結果。

 

numpy – 連立方程式

導入

以下のように行列表示された連立方程式を考える。

     \begin{equation*} \left( \begin{array}{ccc} 1 & 2 & -3 \\ 2 & -1 & 3 \\ -3 & 2 & 1 \end{array} \right) \left( \begin{array}{c} x \\ y \\ z \end{array} \right) = \left( \begin{array}{c} 5 \\ 4 \\ 1 \end{array} \right) \end{equation*}

この方程式の解は、(x, y, z) = (2, 3, 1)

逆行列による方法

係数行列、未知数ベクトル、定数ベクトルをそれぞれ\boldsymbol{A},\boldsymbol{x}, \boldsymbol{b}と表す。

     \begin{equation*} \boldsymbol{A} \boldsymbol{x} = \boldsymbol{b} \end{equation*}

このとき係数行列に逆行列が存在するなら、未知数ベクトルは以下で解ける。

     \begin{gather*} \boldsymbol{A}^{-1} \boldsymbol{A} \boldsymbol{x} = \boldsymbol{A}^{-1} \boldsymbol{b} \\ \boldsymbol{x} = \boldsymbol{A}^{-1} \boldsymbol{b} \\ \end{gather*}

これをnumpy.linalgパッケージの行列操作で解いてみる。

行列にベクトルを掛けるのに、reshape()で行ベクトルから列ベクトルに変換している点に注意。

numpy.linalg.solve()による方法

solve(A, b)関数は、第1引数に係数行列、第2引数に定数ベクトルを与えて、連立方程式の解のベクトルを得ることができる。

非正則行列の場合

以下のような、明らかな非正則行列の場合(連立方程式が不定の場合)、逆行列を計算しようとする時点でsingular matrixのエラーになる。

このようなケースでは、linalg.solve()関数でも同様のエラーとなる。

以下のようなケースはややこしい。同じ係数行列と定数ベクトルに対して、逆行列による解とsolve()による解の値が異なっている。

行列Aの行列式は理論上はゼロであることが確認できる。

 \begin{eqnarray*} \left| \begin{array}{ccc} 1 & 2 &3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array} \right| &=& 1 \cdot (5 \cdot  9 - 6 \cdot 8) - 2 \cdot (4 \cdot 9 - 6 \cdot 7) + 3 \cdot(4 \cdot 8 - 5 \cdot 7) \\ &=& 45 - 48 -2(36 - 42) + 3(32 - 35) \\ &=& -3 +12 + 9 = 0 \end{eqnaray*}

この方程式を掃き出し法で解いていくと以下の通り。

     \begin{equation*} \left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array} \right) \left( \begin{array}{c} x \\ y \\ z \end{array} \right) = \left( \begin{array}{c} 1 \\ 2 \\ 3 \end{array} \right) \end{equation*}

     \begin{equation*} \left( \begin{array}{ccc} 1 & 2 & 3 \\0 & -3 & -6 \\ 0 & -6 & -12 \end{array} \right) \left( \begin{array}{c} x \\ y \\ z \end{array} \right) = \left( \begin{array}{c} 1 & -2 & -4 \end{array} \right) \end{equation*}

     \begin{equation*} \left( \begin{array}{ccc} 1 & 2 & 3 \\0 & -3 & -6 \\ 0 & 0 & 0 \end{array} \right) \left( \begin{array}{c} x \\ y \\ z \end{array} \right) = \left( \begin{array}{c} 1 & -2 & 0 \end{array} \right) \end{equation*}

途中省略するが、ここでzを消去すると、y = -2xとなり、先の計算結果と符合するが、zは0である必要はない。

不定連立方程式において、逆行列やsolve()関数を使って解く場合には注意が必要。

 

numpy – 行列(ndarray)

ベクトルと行列の定義

リテラル

ベクトルはnp.array()で引数にリストを指定して定義。

行列は同じくnp.array()で引数に二次元配列のリストを指定して定義。

単位行列

numpy.identity(n)でn×nの単位行列を生成。

転置

行列の転置にはtranspose()メソッドを使う。代替として.Tとしてもよい。

一次元配列で定義したベクトルにはtranspose()は効かない。列ベクトルに変換するにはreshape()メソッドを使う(reshape(行数, 列数))。

演算

定数倍

ベクトル・行列の定数倍は、各要素の定数倍。

加減

同じ要素数のベクトル、同じ次元の行列同士の下限は要素同士の加減

ベクトルの内積

同じ要素数のベクトルの内積(ドット積)はnp.dot()で計算。

     \begin{equation*} {\bf a} \cdot {\bf b} = \sum_{i=1}^n a_i b_i \end{equation*}

*演算子を使うと、要素ごとの積になる。

行列の積

行列同士の積もnp.dot()で計算。l×m行列とm×n行列の積はl×n行列になる。

     \begin{equation*} \left( \begin{array}{ccc} a_{11} & \cdots  & a_{1m} \\ \vdots & a_{ij} & \vdots \\ a_{l1} & \cdots & a_{lm} \\ \end{array} \right) \cdot \left( \begin{array}{ccc} b_{11} & \cdots & b_{1n} \\ \vdots & b_{jk} & \vdots \\ b_{m1} & \cdots & b_{mn} \\ \end{array}  \right) = \left( \sum_{j=1}^m a_{ij} b_{jk} \right) \end{equation*}

次元数が整合しないとエラーになる。

行ベクトルと行列の積は、ベクトルを前からかけてok。

     \begin{equation*} (1, 2, 3) \left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array} \right) = (30, 36, 42) \end{equation*}

行列と列ベクトルの積は、一次元配列のベクトルをreshape()で列ベクトルに変換してから。

     \begin{equation*} \left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array} \right) \left( \begin{array}{c} 1 \\ 2 \\ 3 \end{array} \right) = \left( \begin{array}{c} 14 \\ 32 \\ 50 \end{array} \right) \end{equation*}

なお、np.dot()の代わりに演算子@が使える。ベクトル同士なら内積、少なくともいずれか一つが行列なら行列積。

numpy.linalgパッケージ

行列式

行列式はnumpy.linalgパッケージのdet()関数で得られる。linalgは”linear algebra”の略で、慣例としてLAという名前で代替される。

逆行列

逆行列はnumpy.linalgパッケージのinv()関数で得られる。

固有値・固有ベクトル

正方行列の固有値と固有ベクトルを、eig()関数で得ることができる(行列の固有値・固有ベクトルの例題を用いた)。

結果は固有値が並んだベクトルと固有ベクトルが並んだ配列で、それぞれを取り出して利用する。なお、固有ベクトルはノルムが1となるように正規化されている。

注意が必要なのは固有ベクトルの方で、各固有ベクトルは配列の列ベクトルとして並んでいる。固有ベクトルを取り出す方法は2通り。

固有値に対応するサフィックスで列ベクトルを取り出す。この方法はnumpyの公式ドキュメントにも以下のように書かれている。

v(…, M, M) array
The normalized (unit “length”) eigenvectors, such that the column v[:,i] is the eigenvector corresponding to the eigenvalue w[i].

固有ベクトルの配列を転置して、行ベクトルの並びにする。

 

行列の固有値・固有ベクトル

概要

行列{\rm A}の固有値・固有ベクトルは以下で定義される。

(1)    \begin{equation*} \boldsymbol{Ax} = \lambda \boldsymbol{x} \end{equation*}

これを以下のように変形する。

(2)    \begin{equation*} (\boldsymbol{A} - \lambda \boldsymbol{I} ) \boldsymbol{x} = {\bf 0} \end{equation*}

この方程式が解をもつためには、以下の条件が必要。

(3)    \begin{equation*} | \boldsymbol{A} - \lambda \boldsymbol{I} | = 0 \end{equation*}

例題

以下の行列に対する固有値、固有ベクトルを求める。

(4)    \begin{equation*} \boldsymbol{A} = \left( \begin{array}{cc} 3 & 1 \\ 2 & 4 \end{array} \right) \end{equation*}

この行列に対する固有値方程式は以下の通り。

(5)    \begin{equation*} | \boldsymbol{A} - \lambda \boldsymbol{I} | = \left| \left( \begin{array}{cc} 3 & 1 \\ 2 & 4 \end{array} \right) - \lambda \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right) \right| = \left| \begin{array}{cc} 3 - \lambda & 1 \\ 2 & 4 - \lambda \end{array} \right| = 0 \end{equation*}

これを解くと、

(6)    \begin{align*} & (3 - \lambda) (4 - \lambda) - 2 = 0 \\ & \lambda ^2 - 7 \lambda + 10 = 0 \\ & (\lambda - 2)(\lambda - 5) = 0 \\ & \lambda = 2, \; 5 \end{align*}

次に、各固有値に対する固有ベクトルを求める。

まず\lambda = 2に対しては、

(7)    \begin{gather*} \left( \begin{array}{cc} 3 - 2 & 1 \\ 2 & 4 - 2 \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{cc} 1 & 1 \\ 2 & 2 \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} 0 \\ 0 \end{array} \right) \\ \Rightarrow \; y = -x \\ \therefore \; \boldsymbol{x} = (t, -t) \end{gather*}

確認してみると、

(8)    \begin{gather*} \boldsymbol{Ax} = \left( \begin{array}{cc} 3 & 1 \\ 2 & 4 \end{array} \right) \left( \begin{array}{c} t \\ -t \end{array} \right) = \left( \begin{array}{c} 2t \\ -2t \end{array} \right) , \quad \lambda \boldsymbol{x} = 2 \left( \begin{array}{c} t \\ -t \end{array} \right) = \left( \begin{array}{c} 2t \\ -2t \end{array} \right) \end{gather*}

また\lambda = 5に対しては、

(9)    \begin{gather*} \left( \begin{array}{cc} 3 - 5 & 1 \\ 2 & 4 - 5 \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{cc} -2 & 1 \\ 2 & -1 \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} 0 \\ 0 \end{array} \right) \\ \Rightarrow \; y = 2x \\ \therefore \; \boldsymbol{x} = (t, 2t) \end{gather*}

こちらも確認してみると、

(10)    \begin{gather*} \boldsymbol{Ax} = \left( \begin{array}{cc} 3 & 1 \\ 2 & 4 \end{array} \right) \left( \begin{array}{c} t \\ 2t \end{array} \right) = \left( \begin{array}{c} 5t \\ 10t \end{array} \right) , \quad \lambda \boldsymbol{x} = 5 \left( \begin{array}{c} t \\ 2t \end{array} \right) = \left( \begin{array}{c} 5t \\ 10t \end{array} \right) \end{gather*}

なお、固有ベクトルを数値で表現する際、ノルムが1となるように正規化することが多い。

(11)    \begin{gather*} \boldsymbol{x} \rightarrow \frac{\boldsymbol{x}}{\| {\boldsymbol{x}} \|} \end{gather*}

上の例で固有値ベクトルを正規化すると以下の通り。

(12)    \begin{gather*} \frac{(t, -t)}{\sqrt{t^2 + t^2}} = \frac{(1, -1)}{\sqrt{2}} \approx (0.7071, -0.7071) \\ \frac{(t, 2t)}{\sqrt{t^2 + 4t^2}} = \frac{(1, 2)}{\sqrt{5}} \approx (0.4472, 0.8944) \end{gather*}

 

ハノイの塔~再帰処理

ハノイの塔とは

ハノイの塔とは、以下のような問題。

  • 3本の棒があり、そのうちの1本に直径が異なる複数の板が直径順に重ねられている
  • 1回の移動で1枚の板を移動するが、移動する板はそれより板がない棒か自身より直径が大きな板がある棒にしか移動できない
  • 全ての板が直径順に、異なる棒に移動し終えたら終了

問題例

たとえば板が3枚の場合は以下のような手順になる。

まず一番下の板を動かすため、

  1. 最小の板を他の棒に移動(0→2)
  2. 次に2番目の板を別の棒に移動(0→1)
  3. 最小の板を2番目の板の上に移動(2→1)
  4. 最大の板を空いている棒に移動(0→2)

なお、3つの棒を左から0、1、2としている。

次に2番目に大きい板を動かすため

  1. 最小の板を空いている棒に移動(1→0)
  2. 2番目の板を最大の板の上に移動(1→2)

最後に1番目の板を2番目の板の上に移動して終了(0→2)

再帰手続き化

これの手続を、次のように一般化する。

まず、n枚の山を3つの軸(org、tmp、dst)のorgからdstに移動する関数を考える。

move(n, org, tmp, dst)

  • n 動かす山の板の枚数
  • org 動かす山がある軸
  • tmp 作業用に使う軸
  • dst 山を動かす先の軸

この関数は、n枚で受け取った山を軸orgから軸dstへ移動するため、この手続きを次のように再帰的に呼び出す。

Step-1:orgからn-1枚の山をtmpに移動。

move(n-1, org, dst, tmp)

Step-2:orgに残った1枚の板をorgに移動

move(1, org, tmp, dst)

Step-3:tmpに移したn-1枚の山をdstに移動

move(n-1, tmp, org, dst)

ただし山の板の枚数が1の場合はそれ以上再帰呼び出しはせず、板があった軸orgと動かした先の軸dstを記録して復帰。

プログラム化

移動過程を軸番号で表示するだけの処理

コード

移動過程を記録するだけならシンプルで、再帰関数を以下のように定義。一枚の板の移動の場合に移動軸を記録・蓄積し、その結果をコンソールに表示している。

実行結果

板が3枚の場合の結果。左側の軸にある一番上の板を、右側の軸に移動することを意味している。

クラス化・画面表示

ハノイの塔を解いていく過程を表示させる。単純なコンソール表示であっても、盤の状態保持やその表示など、コアのアルゴリズムとは別の部分でコードが増える。クラスを作っていくと更にコードが増えるが、全体の見通しはよくなる。

HanoiShaftクラス

盤上の軸のクラス。板を置いたり取り除くほか、任意の位置(高さ)にある板が何か知ることができる。板は直径の小さい順に1, 2, 3,…と整数で表し、軸上の指定位置に板がない場合は0。

Hanoiクラス

盤の状態を保持し、問題を解き、その結果を表示するクラス。問題を解く部分と、実態の盤の状態保持や表示は別のものだが、それらをまとめている。

実行部分

実行結果

板が3枚の場合の結果。

手続回数

もう一度、以下の再帰手続きを考える。

n個の山の計算でn-1個の山の関数を2つ呼び出し、それらがまたn-2個の山の関数を2つずつ呼び出す。

計算回数はこれらの和なので、n個の山における関数の呼び出し回数N_r(n)は以下の通り。

     \begin{equation*} N_r(n) = \sum_{i=1}\n 2^{n-1} = \frac{1 - 2^n}{1 - 2} = 2^n - 1 \end{equation*}

したがって、階乗計算のように一次的な再帰と異なり、nが1増えるごとに計算量が2倍に増えていくことに注意が必要。

 

Python3 – リストの初期化

空のリストの生成

空の場合は添字でアクセスできない。

要素が1個のリストの生成

要素が複数個のリストの生成

最も一般的な、要素をリテラルで指定したリスト。

終わりに”,”をつけても同じ。

要素がない場合はエラー。

多次元のリスト

多次元配列のように定義可能。後ろの方の添字が入れ子の内側のリストの添字。

異なる要素を持つリスト

異なるタイプの要素を持つことができる。

繰り返し指定

*演算子

*演算子で繰り返し数を指定。要素の掛け算ではなく、リストの掛け算のように書く。

これは+演算子によるリストの結合だと考えるとよい。

内包表記

要素が固定の場合。

要素を変化させる場合。

*演算子を使う場合の注意点

*演算子は、同一インスタンスへの参照を複製するだけなので、意図した結果にならない場合がある。

[0, 0]が3つ複製されるが、これらは同じインスタンスを指すため、一つの要素の変更が他にも反映されてしまう。

内包表記なら毎回インスタンスが生成されるので、意図した結果になる。