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

2019-10-22 / tau / コメントする

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

str = '<> < > <abc> <123>'
print(re.findall('<.*>', str))

# ['<> < > <abc> <123>']

str = '<> < > <abc> <123>'

print(re.findall('<.*>', str))

# ['<> < > <abc> <123>']

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

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

print(re.findall('<.*?>', str))

# ['<>', '< >', '<abc>', '<123>']

print(re.findall('<.*?>', str))

# ['<>', '< >', '<abc>', '<123>']

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

print(re.findall('<.+>', str))

# ['<> < > <abc> <123>']

print(re.findall('<.+>', str))

# ['<> < > <abc> <123>']

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

print(re.findall('<.+?>', str))

# ['<> < >', '<abc>', '<123>']

print(re.findall('<.+?>', str))

# ['<> < >', '<abc>', '<123>']

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

print(re.findall('<\w+>', str))

# ['<abc>', '<123>']

print(re.findall('<\w+>', str))

# ['<abc>', '<123>']

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

2019-10-22 / tau / コメントする

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

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

以下のコードで確認。

strings = ['ABCDE', '12345', 'AB+CD', '①②③', '一二三', '壱弐参', '四＋五']

for str in strings:
    print('for', str)
    print('is decimal ->', str.isdecimal())
    print('is digit   ->', str.isdigit())
    print('is numeric ->', str.isnumeric())
    print('is alpha   ->', str.isalpha())
    print('is alnum   ->', str.isalnum())

strings = ['ABCDE', '12345', 'AB+CD', '①②③', '一二三', '壱弐参', '四＋五']

for str in strings:

print('for', str)

print('is decimal ->', str.isdecimal())

print('is digit ->', str.isdigit())

print('is numeric ->', str.isnumeric())

print('is alpha ->', str.isalpha())

print('is alnum ->', str.isalnum())

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

for ABCDE
is decimal -> False
is digit   -> False
is numeric -> False
is alpha   -> True
is alnum   -> True
for 12345
is decimal -> True
is digit   -> True
is numeric -> True
is alpha   -> False
is alnum   -> True

for ABCDE

is decimal -> False

is digit -> False

is numeric -> False

is alpha -> True

is alnum -> True

for 12345

is decimal -> True

is digit -> True

is numeric -> True

is alpha -> False

is alnum -> True

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

for AB+CD
is decimal -> False
is digit   -> False
is numeric -> False
is alpha   -> False
is alnum   -> False

for AB+CD

is decimal -> False

is digit -> False

is numeric -> False

is alpha -> False

is alnum -> False

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

for ①②③
is decimal -> False
is digit   -> True
is numeric -> True
is alpha   -> False
is alnum   -> True

for ①②③

is decimal -> False

is digit -> True

is numeric -> True

is alpha -> False

is alnum -> True

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

for 一二三
is decimal -> False
is digit   -> False
is numeric -> True
is alpha   -> True
is alnum   -> True
for 壱弐参
is decimal -> False
is digit   -> False
is numeric -> True
is alpha   -> True
is alnum   -> True

for 一二三

is decimal -> False

is digit -> False

is numeric -> True

is alpha -> True

is alnum -> True

for 壱弐参

is decimal -> False

is digit -> False

is numeric -> True

is alpha -> True

is alnum -> True

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

for 四＋五
is decimal -> False
is digit   -> False
is numeric -> False
is alpha   -> False
is alnum   -> False

for 四＋五

is decimal -> False

is digit -> False

is numeric -> False

is alpha -> False

is alnum -> False

Python – コマンドライン引数

2019-10-22 / tau / コメントする

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

以下のような仕様

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

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

import sys

args = sys.argv

print('number of afgs {}'.format(len(args)))
print(args)
for arg in args:
    print(arg)

import sys

args = sys.argv

print('number of afgs {}'.format(len(args)))

print(args)

for arg in args:

print(arg)

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

C:\>cmd_arg.py
number of afgs 1
['C:\\cmd_arg.py']
C:\cmd_arg.py

C:\>cmd_arg.py

number of afgs 1

['C:\\cmd_arg.py']

C:\cmd_arg.py

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

C:\>cmd_arg.py 123 abc 'abc'
number of afgs 4
['C:\\cmd_arg.py', '123', 'abc', "'abc'"]
C:\cmd_arg.py
123
abc
'abc'

C:\>cmd_arg.py 123 abc 'abc'

number of afgs 4

['C:\\cmd_arg.py', '123', 'abc', "'abc'"]

C:\cmd_arg.py

123

abc

'abc'

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

import sys

args = sys.argv

print('number of afgs {}'.format(len(args)))
args = args[1:]
if len(args) == 0:
    print('no arguments')
    sys.exit()

print(args)
for arg in args:
    if arg.isdecimal():
        print('{} is decimal -> {}'.format(arg, int(arg) * 2))
    else:
        print('{} is not decimal'.format(arg))

import sys

args = sys.argv

print('number of afgs {}'.format(len(args)))

args = args[1:]

if len(args) == 0:

print('no arguments')

sys.exit()

print(args)

for arg in args:

if arg.isdecimal():

print('{} is decimal -> {}'.format(arg, int(arg) * 2))

else:

print('{} is not decimal'.format(arg))

実行結果。

C:\>cmd_arg_dight_check.py
number of afgs 1
no arguments

C:\>cmd_arg_dight_check.py ABC 123
number of afgs 3
['ABC', '123']
ABC is not decimal
123 is decimal -> 246

C:\>cmd_arg_dight_check.py

number of afgs 1

no arguments

C:\>cmd_arg_dight_check.py ABC 123

number of afgs 3

['ABC', '123']

ABC is not decimal

123 is decimal -> 246

numpy – 連立方程式

2019-10-21 / tau / コメントする

導入

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

$\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()で行ベクトルから列ベクトルに変換している点に注意。

A = np.array([[1, 2, -3],
              [2, -1, 3],
              [-3, 2, 1]])

b = np.array([5, 4, 1])
print(LA.inv(A) @ b.reshape(3, 1))

# [[2.]
#  [3.]
#  [1.]]

A = np.array([[1, 2, -3],

[2, -1, 3],

[-3, 2, 1]])

b = np.array([5, 4, 1])

print(LA.inv(A) @ b.reshape(3, 1))

# [[2.]

# [3.]

# [1.]]

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

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

A = np.array([[1, 2, -3],
              [2, -1, 3],
              [-3, 2, 1]])

b = np.array([5, 4, 1])
print(LA.solve(A, b))

# [2. 3. 1.]

A = np.array([[1, 2, -3],

[2, -1, 3],

[-3, 2, 1]])

b = np.array([5, 4, 1])

print(LA.solve(A, b))

# [2. 3. 1.]

非正則行列の場合

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

A = np.array([[1, 1], [2, 2]])
b = np.array([2, 4])
print(LA.inv(A))

# numpy.linalg.LinAlgError: Singular matrix

A = np.array([[1, 1], [2, 2]])

b = np.array([2, 4])

print(LA.inv(A))

# numpy.linalg.LinAlgError: Singular matrix

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

A = np.array([[1, 1], [2, 2]])
b = np.array([2, 4])
print(LA.solve(A, b))

# numpy.linalg.LinAlgError: Singular matrix

A = np.array([[1, 1], [2, 2]])

b = np.array([2, 4])

print(LA.solve(A, b))

# numpy.linalg.LinAlgError: Singular matrix

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

A = np.array([[1, 2, 3],
              [4, 5, 6],
              [7, 8, 9]])
b = np.array([1, 2, 3])
print(LA.det(A))
print(LA.inv(A) @ b.reshape(3, 1))
print(LA.solve(A, b))

# 6.66133814775094e-16
# [[ 2.]
#  [-4.]
#  [ 0.]]
# [-0.33333333  0.66666667  0.        ]

A = np.array([[1, 2, 3],

[4, 5, 6],

[7, 8, 9]])

b = np.array([1, 2, 3])

print(LA.det(A))

print(LA.inv(A) @ b.reshape(3, 1))

print(LA.solve(A, b))

# 6.66133814775094e-16

# [[ 2.]

# [-4.]

# [ 0.]]

# [-0.33333333 0.66666667 0. ]

行列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)

2019-10-20 / tau / コメントする

ベクトルと行列の定義

リテラル

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

v = np.array([1, 2, 3])
print(v)

# [1 2 3]

v = np.array([1, 2, 3])

print(v)

# [1 2 3]

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

m = np.array([[1, 2, 3], [4, 5, 6]])
print(m)

# [[1 2 3]
#  [4 5 6]]

m = np.array([[1, 2, 3], [4, 5, 6]])

print(m)

# [[1 2 3]

# [4 5 6]]

単位行列

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

print(np.identity(4))

# [[1. 0. 0. 0.]
#  [0. 1. 0. 0.]
#  [0. 0. 1. 0.]
#  [0. 0. 0. 1.]]

print(np.identity(4))

# [[1. 0. 0. 0.]

# [0. 1. 0. 0.]

# [0. 0. 1. 0.]

# [0. 0. 0. 1.]]

転置

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

m = np.array([[1, 2, 3], [4, 5, 6]])
print(m.transpose())
print(m.T)

# [[1 4]
#  [2 5]
#  [3 6]]
# [[1 4]
#  [2 5]
#  [3 6]]

m = np.array([[1, 2, 3], [4, 5, 6]])

print(m.transpose())

print(m.T)

# [[1 4]

# [2 5]

# [3 6]]

# [[1 4]

# [2 5]

# [3 6]]

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

v = np.array([1, 2, 3])
print(v.T)
print(v.reshape(3, 1))

# [1 2 3]
# [[1]
#  [2]
#  [3]]

v = np.array([1, 2, 3])

print(v.T)

print(v.reshape(3, 1))

# [1 2 3]

# [[1]

# [2]

# [3]]

演算

定数倍

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

a = 2
v = np.array([1, 2, 3])
m = np.array([[1, 2, 3], [4, 5, 6]])

print(a*v)
print(a*m)

# [2 4 6]
# [[ 2  4  6]
#  [ 8 10 12]]

a = 2

v = np.array([1, 2, 3])

m = np.array([[1, 2, 3], [4, 5, 6]])

print(a*v)

print(a*m)

# [2 4 6]

# [[ 2 4 6]

# [ 8 10 12]]

加減

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

a = np.array([1, 2, 3])
b = np.array([2, 4, 6])
A = np.array([[1, 2], [3, 4]])
B = np.array([[2, 4], [6, 8]])

print(a + b)
print(a - b)
print(A + B)
print(A - B)

# [3 6 9]
# [-1 -2 -3]
# [[ 3  6]
#  [ 9 12]]
# [[-1 -2]
#  [-3 -4]]

a = np.array([1, 2, 3])

b = np.array([2, 4, 6])

A = np.array([[1, 2], [3, 4]])

B = np.array([[2, 4], [6, 8]])

print(a + b)

print(a - b)

print(A + B)

print(A - B)

# [3 6 9]

# [-1 -2 -3]

# [[ 3 6]

# [ 9 12]]

# [[-1 -2]

# [-3 -4]]

ベクトルの内積

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

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

a = np.array([1, 2, 3])
b = np.array([4, 5, 6])
print(np.dot(a, b))

# 32

a = np.array([1, 2, 3])

b = np.array([4, 5, 6])

print(np.dot(a, b))

# 32

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

print(a*b)

# [ 4 10 18]

print(a*b)

# [ 4 10 18]

行列の積

行列同士の積も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*}$

A = np.array([[1, 2, 3],
              [4, 5, 6]])
B = np.array([[1, 2],
              [3, 4],
              [5, 6]])
print(np.dot(A, B))

# [[22 28]
#  [49 64]]

A = np.array([[1, 2, 3],

[4, 5, 6]])

B = np.array([[1, 2],

[3, 4],

[5, 6]])

print(np.dot(A, B))

# [[22 28]

# [49 64]]

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

A = np.array([[1, 2, 3],
              [4, 5, 6]])
B = np.array([[1, 2],
              [3, 4]])
print(np.dot(A, B))

# ValueError: shapes (2,3) and (2,2) not aligned: 3 (dim 1) != 2 (dim 0)

A = np.array([[1, 2, 3],

[4, 5, 6]])

B = np.array([[1, 2],

[3, 4]])

print(np.dot(A, B))

# ValueError: shapes (2,3) and (2,2) not aligned: 3 (dim 1) != 2 (dim 0)

行ベクトルと行列の積は、ベクトルを前からかけて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*}$

a = np.array([1, 2, 3])
A = np.array([[1, 2, 3],
              [4, 5, 6],
              [7, 8, 9]])
print(np.dot(a, A))

# [30 36 42]

a = np.array([1, 2, 3])

A = np.array([[1, 2, 3],

[4, 5, 6],

[7, 8, 9]])

print(np.dot(a, A))

# [30 36 42]

行列と列ベクトルの積は、一次元配列のベクトルを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*}$

A = np.array([[1, 2, 3],
              [4, 5, 6],
              [7, 8, 9]])
a = np.array([1, 2, 3]).reshape(3, 1)
print(np.dot(A, a))

# [[14]
#  [32]
#  [50]]

A = np.array([[1, 2, 3],

[4, 5, 6],

[7, 8, 9]])

a = np.array([1, 2, 3]).reshape(3, 1)

print(np.dot(A, a))

# [[14]

# [32]

# [50]]

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

a = np.array([1, 2])
b = np.array([1, 2, 3]).reshape(3, 1)
A = np.array([[1, 2, 3],
              [4, 5, 6]])
B = np.array([[1, 2],
              [3, 4],
              [5, 6]])
print(a @ a)
print(a @ A)
print(A @ b)
print(A @ B)

# 5
# [ 9 12 15]
# [[14]
#  [32]]
# [[22 28]
#  [49 64]]

a = np.array([1, 2])

b = np.array([1, 2, 3]).reshape(3, 1)

A = np.array([[1, 2, 3],

[4, 5, 6]])

B = np.array([[1, 2],

[3, 4],

[5, 6]])

print(a @ a)

print(a @ A)

print(A @ b)

print(A @ B)

# 5

# [ 9 12 15]

# [[14]

# [32]]

# [[22 28]

# [49 64]]

numpy.linalgパッケージ

行列式

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

import numpy.linalg as LA

A = np.array([[1, 2],
              [3, 4]])
B = np.array([[1, 2, 3],
              [2, 1, 3],
              [3, 1, 2]])

print(LA.det(A))
print(LA.det(B))

# -2.0000000000000004
# 6.000000000000001

import numpy.linalg as LA

A = np.array([[1, 2],

[3, 4]])

B = np.array([[1, 2, 3],

[2, 1, 3],

[3, 1, 2]])

print(LA.det(A))

print(LA.det(B))

# -2.0000000000000004

# 6.000000000000001

逆行列

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

A = np.array([[1, 2],
              [3, 4]])
B = np.array([[1, 2, 3],
              [2, 1, 3],
              [3, 1, 2]])

print(LA.inv(A))
print(LA.inv(B))

# [[-2.   1. ]
#  [ 1.5 -0.5]]
# [[-0.16666667 -0.16666667  0.5       ]
#  [ 0.83333333 -1.16666667  0.5       ]
#  [-0.16666667  0.83333333 -0.5       ]]

A = np.array([[1, 2],

[3, 4]])

B = np.array([[1, 2, 3],

[2, 1, 3],

[3, 1, 2]])

print(LA.inv(A))

print(LA.inv(B))

# [[-2. 1. ]

# [ 1.5 -0.5]]

# [[-0.16666667 -0.16666667 0.5 ]

# [ 0.83333333 -1.16666667 0.5 ]

# [-0.16666667 0.83333333 -0.5 ]]

固有値・固有ベクトル

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

A = np.array([[3, 1],
              [2, 4]])
print(LA.eig(A))

# (array([2., 5.]), array([[-0.70710678, -0.4472136 ],
#        [ 0.70710678, -0.89442719]]))

A = np.array([[3, 1],

[2, 4]])

print(LA.eig(A))

# (array([2., 5.]), array([[-0.70710678, -0.4472136 ],

# [ 0.70710678, -0.89442719]]))

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

eigenvalues, eigenvectors = LA.eig(A)
print(eigenvalues)
print(eigenvectors)

# [2. 5.]
# [[-0.70710678 -0.4472136 ]
#  [ 0.70710678 -0.89442719]]

eigenvalues, eigenvectors = LA.eig(A)

print(eigenvalues)

print(eigenvectors)

# [2. 5.]

# [[-0.70710678 -0.4472136 ]

# [ 0.70710678 -0.89442719]]

注意が必要なのは固有ベクトルの方で、各固有ベクトルは配列の列ベクトルとして並んでいる。固有ベクトルを取り出す方法は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].

print(eigenvectors[:,0], eigenvectors[:,1])

# [-0.70710678  0.70710678] [-0.4472136  -0.89442719]

print(eigenvectors[:,0], eigenvectors[:,1])

# [-0.70710678 0.70710678] [-0.4472136 -0.89442719]

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

eigenvectors = eigenvectors.T
print(eigenvectors[0], eigenvectors[1])

# [-0.70710678 0.70710678] [-0.4472136 -0.89442719]

eigenvectors = eigenvectors.T

print(eigenvectors[0], eigenvectors[1])

# [-0.70710678 0.70710678] [-0.4472136 -0.89442719]

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

2019-10-20 / tau / コメントする

概要

行列 ${\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*}$

ハノイの塔～再帰処理

2019-10-05 / tau / コメントする

ハノイの塔とは

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

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

問題例

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

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

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

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

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

最小の板を空いている棒に移動(1→0)
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を記録して復帰。

プログラム化

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

コード

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

def move(n, org, tmp, dst, solution):
    if n == 1:
        solution.append((org, dst))
        return
    else:
        move(n-1, org, dst, tmp, solution)
        move(1, org, tmp, dst, solution)
        move(n-1, tmp, org, dst, solution)


org, tmp, dst = 0, 1, 2
n = 3
solution = []

move(n, org, tmp, dst, solution)

for movement in solution: print(movement)

def move(n, org, tmp, dst, solution):

if n == 1:

solution.append((org, dst))

return

else:

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

move(1, org, tmp, dst, solution)

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

org, tmp, dst = 0, 1, 2

n = 3

solution = []

move(n, org, tmp, dst, solution)

for movement in solution: print(movement)

実行結果

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

(0, 2)
(0, 1)
(2, 1)
(0, 2)
(1, 0)
(1, 2)
(0, 2)

(0, 2)

(0, 1)

(2, 1)

(0, 2)

(1, 0)

(1, 2)

(0, 2)

クラス化・画面表示

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

HanoiShaftクラス

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

class HanoiShaft:
    def __init__(self):
        self.shaft = []

    def disk_at(self, layer):
        return 0 if len(self.shaft) < layer + 1 else self.shaft[layer]

    def put(self, disk):
        self.shaft.append(disk)

    def remove(self):
        return self.shaft.pop()

class HanoiShaft:

def __init__(self):

self.shaft = []

def disk_at(self, layer):

return 0 if len(self.shaft) < layer + 1 else self.shaft[layer]

def put(self, disk):

self.shaft.append(disk)

def remove(self):

return self.shaft.pop()

Hanoiクラス

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

class Hanoi:
    def __init__(self, num_disks):
        self.num_disks = num_disks
        self.solution = []
        self.shafts = [HanoiShaft() for n in range(3)]
        org, tmp, dst = 0, 1, 2
        for disk in range(num_disks, 0, -1):
            self.shafts[org].put(disk)

    def solve(self):
        self.solution = []
        self.move(self.num_disks, 0, 1, 2)

    def move(self, n, org, tmp, dst):
        if n == 1:
            self.solution.append((org, dst))
            return
        else:
            self.move(n-1, org, dst, tmp)
            self.move(1, org, tmp, dst)
            self.move(n-1, tmp, org, dst)

    def display_solution(self):
        self.display_status()
        self.solve()
        for movement in self.solution:
            disk = self.shafts[movement[0]].remove()
            self.shafts[movement[1]].put(disk)
            self.display_status()

    def display_status(self):
        max_width = self.num_disks * 2 - 1
        for layer in range(self.num_disks-1, -1, -1):
            layer_str = ''
            for shaft in self.shafts:
                disk = shaft.disk_at(layer)
                if disk == 0:
                    space_size = (max_width - 1) // 2
                    layer_str += ' '*space_size + '|' + ' '*space_size + ' '
                else:
                    disk_size = disk * 2 - 1
                    space_size = (max_width - disk_size) // 2
                    layer_str += \
                        ' '*space_size + '#'*disk_size + ' '*space_size + ' '
            print(layer_str)
        print('-'*(max_width*3+2))
        print()

class Hanoi:

def __init__(self, num_disks):

self.num_disks = num_disks

self.solution = []

self.shafts = [HanoiShaft() for n in range(3)]

org, tmp, dst = 0, 1, 2

for disk in range(num_disks, 0, -1):

self.shafts[org].put(disk)

def solve(self):

self.solution = []

self.move(self.num_disks, 0, 1, 2)

def move(self, n, org, tmp, dst):

if n == 1:

self.solution.append((org, dst))

return

else:

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

self.move(1, org, tmp, dst)

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

def display_solution(self):

self.display_status()

self.solve()

for movement in self.solution:

disk = self.shafts[movement[0]].remove()

self.shafts[movement[1]].put(disk)

self.display_status()

def display_status(self):

max_width = self.num_disks * 2 - 1

for layer in range(self.num_disks-1, -1, -1):

layer_str = ''

for shaft in self.shafts:

disk = shaft.disk_at(layer)

if disk == 0:

space_size = (max_width - 1) // 2

layer_str += ' '*space_size + '|' + ' '*space_size + ' '

else:

disk_size = disk * 2 - 1

space_size = (max_width - disk_size) // 2

layer_str += \

' '*space_size + '#'*disk_size + ' '*space_size + ' '

print(layer_str)

print('-'*(max_width*3+2))

print()

実行部分

hanoi = Hanoi(3)
hanoi.display_solution()

1 2	hanoi = Hanoi(3) hanoi.display_solution()

実行結果

板が3枚の場合の結果。

  #     |     |   
 ###    |     |   
#####   |     |   
-----------------

  |     |     |   
 ###    |     |   
#####   |     #   
-----------------

  |     |     |   
  |     |     |   
#####  ###    #   
-----------------

  |     |     |   
  |     #     |   
#####  ###    |   
-----------------

  |     |     |   
  |     #     |   
  |    ###  ##### 
-----------------

  |     |     |   
  |     |     |   
  #    ###  ##### 
-----------------

  |     |     |   
  |     |    ###  
  #     |   ##### 
-----------------

  |     |     #   
  |     |    ###  
  |     |   ##### 
-----------------

# | |

### | |

##### | |

-----------------

| | |

### | |

##### | #

-----------------

| | |

##### ### #

-----------------

| | |

| # |

##### ### |

-----------------

| | |

| # |

| ### #####

-----------------

| | |

# ### #####

-----------------

| | |

| | ###

# | #####

-----------------

| | #

| | ###

| | #####

-----------------

手続回数

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

def move(n, org, tmp, dst, solution):
    if n == 1:
        solution.append((org, dst))
        return
    else:
        move(n-1, org, dst, tmp, solution)
        move(1, org, tmp, dst, solution)
        move(n-1, tmp, org, dst, solution)

def move(n, org, tmp, dst, solution):

if n == 1:

solution.append((org, dst))

return

else:

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

move(1, org, tmp, dst, solution)

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

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 – リストの初期化

2019-10-03 / tau / コメントする

空のリストの生成

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

lst = []
print(len(lst)) # 0
print(lst)      # []
print(lst[0])   # Error: list index out of range

lst = []

print(len(lst)) # 0

print(lst) # []

print(lst[0]) # Error: list index out of range

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

lst = [2]
print(len(lst)) # 1
print(lst)      # [1]
print(lst[0])   # 2

lst = [2]

print(len(lst)) # 1

print(lst) # [1]

print(lst[0]) # 2

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

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

lst = [1, 2]
print(len(lst))       # 2
print(lst)            # [1, 2]
print(lst[0], lst[1]) # 1 2

lst = [1, 2]

print(len(lst)) # 2

print(lst) # [1, 2]

print(lst[0], lst[1]) # 1 2

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

lst = [1, 2,]
print(lst) # [1, 2]

1 2	lst = [1, 2,] print(lst) # [1, 2]

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

lst = [,] # Error: invalid syntax

1	lst = [,] # Error: invalid syntax

多次元のリスト

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

lst = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
print(lst[0][1], lst[2][1]) # 1 7

1 2	lst = [[0, 1, 2], [3, 4, 5], [6, 7, 8]] print(lst[0][1], lst[2][1]) # 1 7

異なる要素を持つリスト

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

lst = [1, 'two', [3, 'four']]
print(len(lst))  # 3
print(lst[1])    # two
print(lst[2])    # [3, 'four']
print(lst[1][0]) # t
print(lst[2][1]) # four

lst = [1, 'two', [3, 'four']]

print(len(lst)) # 3

print(lst[1]) # two

print(lst[2]) # [3, 'four']

print(lst[1][0]) # t

print(lst[2][1]) # four

繰り返し指定

*演算子

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

lst1 = [0]*3
lst2 = [1, 2]*3
print(lst1) # [0, 0, 0]
print(lst2) # [1, 2, 1, 2, 1, 2]

lst1 = [0]*3

lst2 = [1, 2]*3

print(lst1) # [0, 0, 0]

print(lst2) # [1, 2, 1, 2, 1, 2]

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

lst = [0] + [0] + [0]
print(lst) # [0, 0, 0]

1 2	lst = [0] + [0] + [0] print(lst) # [0, 0, 0]

内包表記

要素が固定の場合。

lst = [0 for n in range(3)]
print(lst) # [0, 0, 0]

1 2	lst = [0 for n in range(3)] print(lst) # [0, 0, 0]

要素を変化させる場合。

lst = [n*2 for n in range(3)]
print(lst) [0, 2, 4]

1 2	lst = [n*2 for n in range(3)] print(lst) [0, 2, 4]

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

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

lst = [[0]*2]*3
print(lst)    # [[0, 0], [0, 0], [0, 0]]
lst[0][0] = 1
print(lst)    # [[1, 0], [1, 0], [1, 0]]

lst = [[0]*2]*3

print(lst) # [[0, 0], [0, 0], [0, 0]]

lst[0][0] = 1

print(lst) # [[1, 0], [1, 0], [1, 0]]

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

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

lst = [[0]*2 for n in range(3)]
print(lst)    # [[0, 0], [0, 0], [0, 0]]
lst[0][0] = 1
print(lst)    # [[1, 0], [0, 0], [0, 0]]

lst = [[0]*2 for n in range(3)]

print(lst) # [[0, 0], [0, 0], [0, 0]]

lst[0][0] = 1

print(lst) # [[1, 0], [0, 0], [0, 0]]