[解決済み] Pythonで2つのリストが循環的に同一であるかどうかを確認する方法

質問

例えば、リストがあります。

a[0] = [1, 1, 1, 0, 0]
a[1] = [1, 1, 0, 0, 1]
a[2] = [0, 1, 1, 1, 0]
# and so on

それぞれ異なるように見えますが、始点と終点がつながっていると仮定すれば、両者は 円形に は同じです。

問題は、私が持っている各リストの長さが55で、その中に3つの1と52の0しか含まれていないことです。循環条件なしの場合、リストは26,235個（55から3を選択）あります。しかし、条件「循環的」が存在する場合、膨大な数の循環的に同一のリストが存在します。

現在、私は以下の方法で循環的同一性を確認しています。

def is_dup(a, b):
    for i in range(len(a)):
        if a == list(numpy.roll(b, i)): # shift b circularly by i
            return True
    return False

この関数では、最悪の場合、55回の周期的なシフト操作が必要です。そして、互いに比較されるリストが26,235個あります。つまり、55 * 26,235 * (26,235 - 1) / 2 = 18,926,847,225 の計算が必要なんです。およそ20ギガ近い計算量だ!

もっと少ない計算回数でできる良い方法はないでしょうか？あるいは サーキュラー ?

解決方法は？

まず、これは O(n) リストの長さの点で もし、あなたがリストを2回複製するのであれば、気づくことができるでしょう( [1, 2, 3] になります。 [1, 2, 3, 1, 2, 3] であれば、新しいリストは間違いなくすべての可能な環状リストを保持することになります。

つまり、検索するリストが開始リストの2倍以内にあるかどうかをチェックすればよいのです。Pythonでは、以下の方法でこれを実現できます（長さが同じであると仮定します）。

list1 = [1, 1, 1, 0, 0]
list2 = [1, 1, 0, 0, 1]
print ' '.join(map(str, list2)) in ' '.join(map(str, list1 * 2))

私のワンライナーについて少し説明します。 list * 2 は、リストとそれ自身を結合します。 map(str, [1, 2]) はすべての数値を文字列に変換し ' '.join() は、配列 ['1', '2', '111'] を文字列に変換します。 '1 2 111' .

コメントで指摘されたように、onelinerは誤検出の可能性があるため、可能な限りのエッジケースをカバーするようにしました。

def isCircular(arr1, arr2):
    if len(arr1) != len(arr2):
        return False

    str1 = ' '.join(map(str, arr1))
    str2 = ' '.join(map(str, arr2))
    if len(str1) != len(str2):
        return False

    return str1 in str2 + ' ' + str2

P.S.1 時間の複雑さについて語るとき、注目すべきなのは O(n) で部分文字列が見つかれば達成されます。 O(n) の時間です。必ずしもそうではなく、あなたの言語での実装に依存します ( とはいえ、潜在的にはリニアに実行できる 時間KMPなど)。

P.S.2 文字列操作に恐怖を感じ、そのために答えがよくないと思っている人へ。重要なのは、複雑さとスピードです。このアルゴリズムは、潜在的に O(n) 時間と O(n) のものよりはるかに優れています。 O(n^2) ドメインになります。これを自分で見るには、小さなベンチマークを実行することができます（ランダムなリストを作成し、最初の要素をポップし、それを最後に追加して、循環リストを作成します。自由に操作してください)

from random import random
bigList = [int(1000 * random()) for i in xrange(10**6)]
bigList2 = bigList[:]
bigList2.append(bigList2.pop(0))

# then test how much time will it take to come up with an answer
from datetime import datetime
startTime = datetime.now()
print isCircular(bigList, bigList2)
print datetime.now() - startTime    # please fill free to use timeit, but it will give similar results

私のマシンでは0.3秒。そんなに長くはないですね。では、これを O(n^2) のソリューションを提供します。比較する間に、アメリカからオーストラリアに旅行することができます（おそらくクルーズ船で）。