Determinant (Ice Base) - 行列式

どんな問題？

Determinant
http://www.checkio.org/mission/determinant/

行列式を求めよ。

引数は、行列が list of list で渡される。最大で5x5の行列まで。
戻り値は、行列式の値を int で返す。

例題：

checkio([[4,3], [6,3]]) == -6
 
checkio([[1, 3, 2],
         [1, 1, 4],
         [2, 2, 1]]) == 14

どうやって解く？

行列式の計算式は以下のリンクを参考にした。

• 線形代数を学ぼう その５ - 行列式　←わかりやすかった
• 線形代数入門 - 行列式
• 行列式 - Wikipedia

2x2行列なら普通に行列式を計算し、それ以上なら余因子展開を使って、再帰で行列式を求める。

• 行列の左端の数字を上から順に1つ選ぶ → data[i][0]
• その数字の余因子行列を求めて、再帰で行列式を計算 → chekio(get_cofactor(i))
• iが偶数なら符号は+、基数なら符号は-とする → (-1)**i

def checkio(data):
    def get_cofactor(index):
        return [data[i][1:] for i in range(len(data)) if i != index]

    if len(data) == 2:
        return data[0][0] * data[1][1] - data[1][0] * data[0][1]
    else:
        # 余因子展開
        return sum(((-1) ** i * data[i][0] * checkio(get_cofactor(i))) for i in range(len(data)))

実行すると、checkio([ [1] ])のときにエラーになってしまった。
1x1の場合を考えてなかったので修正。1x1の行列式は、|a| = a でいいみたいだ。

まとめ

def checkio(data):
    def get_cofactor(index):
        return [data[i][1:] for i in range(len(data)) if i != index]
 
    if len(data) == 1:
        return data[0][0]
    elif len(data) == 2:
        return data[0][0] * data[1][1] - data[1][0] * data[0][1]
    else:
        return sum(((-1) ** i * data[i][0] * checkio(get_cofactor(i))) for i in range(len(data)))

http://www.checkio.org/mission/determinant/publications/natsuki/python-3/first/

追記

Sim0000さんから、この2行が不要だとのコメントがあって、見直してみると、確かに2x2行列の場合も余因子展開に含めることができる。気付かなかった。ご指摘に感謝！

    elif len(data) == 2:
        return data[0][0] * data[1][1] - data[1][0] * data[0][1]

修正したのがこちら。

def checkio(data):
    def get_cofactor(index):
        return [data[i][1:] for i in range(len(data)) if i != index]
 
    if len(data) == 1:
        return data[0][0]
    else:
        return sum(((-1) ** i * data[i][0] * checkio(get_cofactor(i))) for i in range(len(data)))