Pythonで行列のすべての行が互いに循環回転の関係にあるかどうかを判定する方法

n×n のサイズを持つ行列が与えられます。各要素には整数や文字などが格納されています。ここでの課題は、行列のすべての行が、その直前の行の循環回転（circular rotation）になっているかどうかを判定することです。なお、最初の行に関しては、最後の行（n 行目）の循環回転であることが条件となります。

たとえば、次のような入力が与えられた場合を考えてみましょう。

この場合、各行は前の行を1つずつ回転させたものになっているため、出力は True となります。

解法のアプローチ

この問題を解く鍵となるのは、「文字列をそれ自身と連結すると、元の文字列のすべての循環回転パターンが部分文字列として含まれる」という有名なテクニックです。手順は以下の通りです。

• 空の文字列 concat を用意します。
• 0 行目の各要素を、区切り文字「-」とともに concat へ順に連結していきます。
• concat をもう一度自分自身と連結し、長さを2倍にします。
• 1 行目以降の各行についても同様に文字列化し、その文字列が concat の中に含まれているかを確認します。
• 含まれていれば True を返し、1 行でも一致しないものがあれば False を返します。

なぜ文字列を2倍にするのか？

ある文字列 S を S+S の形にすると、S のあらゆる循環回転が必ずその内部に現れます。これにより、各行を実際に回転させながら逐一比較する必要がなくなり、単純な部分文字列検索だけで判定できるようになります。また、隣接する要素が誤って連結されるのを防ぐため、区切り文字として「-」を挿入しています。

実装例

それでは、実際の実装を見てみましょう。

def solve(matrix):
    concat = ''
    for i in range(len(matrix)):
        concat = concat + '-' + str(matrix[0][i])
    concat = concat + concat
    for i in range(1, len(matrix)):
        curr_row = ''
        for j in range(len(matrix[0])):
            curr_row = curr_row + '-' + str(matrix[i][j])
        if concat.find(curr_row) != -1:
            return True
    return False

matrix = [['B', 'A', 'D', 'C'],
          ['C', 'B', 'A', 'D'],
          ['D', 'C', 'B', 'A'],
          ['A', 'D', 'C', 'B']]

print(solve(matrix))

注意点として、find() メソッドは対象が見つからない場合に -1 を返します。-1 は Python では真と評価されてしまうため、必ず != -1 という形で比較することが重要です。

入力

[['B', 'A', 'D', 'C'],
['C', 'B', 'A', 'D'],
['D', 'C', 'B', 'A'],
['A', 'D', 'C', 'B']]

出力

True

計算量について

文字列の構築には O(n²) の時間がかかり、各行の部分文字列検索も Python の str.find() が採用する効率的なアルゴリズムによって高速に処理されます。使用する補助メモリは、倍長になった文字列と現在処理中の行の文字列のみで、空間計算量は O(n) に抑えられます。