循環データを比較する速い方法

Question

データセット{A、B、C、D}が任意のタイプで、別のデータセットと比較したいとします。私は{A、B、C、D}、{B、C、D、A}、{C、D、A、B}、{D、A、B、C} {A、C、B、D}または同様に注文されていない他のセットではありません。これを行うための速い方法は何ですか？

それらを配列に格納し、回転させ、そのように比較することは、O（n^2）タスクであり、あまり良くありません。

私の最初の直感は、データを{A、B、C、D、A、B、C}のようなセットとして保存し、O（n）だけのサブセットを検索することです。これはもっと速くできますか？

Answer 1

文字列の最小回転を見つけるための高速アルゴリズム - https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotationがあります。したがって、最小回転を保存して比較することができます。

Answer 2

1つのオプションは、有向グラフを使用することです。次の遷移を含むグラフを設定します。

A -> B 
B -> C 
C -> D 
D -> A 

他のすべてのトランジションでは、エラー状態になります。したがって、各メンバーがユニークであれば（をに設定することによって暗示されます）、開始した同じグラフノードで終了したメンバーシップを特定できます。

値が複数回表示される場合は、よりスマートな状態と遷移が必要です。

この方法は、1回の検索を事前に計算し、それを多数のデータポイントに一致させる場合に便利です。グラフを常に再生成する必要がある場合はあまり役に立ちません。状態テーブルが大きい場合は、キャッシュが非効率的になる可能性もあります。

Answer 3

まあ、博士ゾイドバーグは、あなたが注文に興味があるならば、あなたは順序を保つ構造にあなたのデータを格納する必要があり、また簡単に回転することができます。 リストでは、Pythonでそれができます。

リストの最小の要素を見つけて、最小の要素が最初に来るまで、比較する各リストを回転させます。注：これはソートではなく、回転です。比較のためのすべてのリストが標準化されているので、任意の2つの間の直線リスト比較は、回転後も同じであるかどうかを判断します。

>>> def rotcomp(lst1, lst2): 
    while min(lst1) != lst1[0]: 
     lst1 = lst1[1:] + [lst1[0]] 
    while min(lst2) != lst2[0]: 
     lst2 = lst2[1:] + [lst2[0]] 
    return lst1 == lst2 

>>> rotcomp(list('ABCD'), list('CDAB')) 
True 
>>> rotcomp(list('ABCD'), list('CDBA')) 
False 
>>> 
>>> rotcomp(list('AABC'), list('ABCA')) 
False 
>>> def rotcomp2(lst1, lst2): 
    return repr(lst1)[1:-1] in repr(lst2 + lst2) 

>>> rotcomp2(list('ABCD'), list('CDAB')) 
True 
>>> rotcomp2(list('ABCD'), list('CDBA')) 
False 
>>> rotcomp2(list('AABC'), list('ABCA')) 
True 
>>> 

NEWセクション：デュプリケート？

入力に重複が含まれている可能性があります（質問の下に記載されている双子の質問から）。アルゴリズムは、一方のリストがもう一方のリストのサブリストであるかどうかを確認することです。

関数rotcomp2は、そのアルゴリズムとリスト内容のreprのテキスト比較を使用します。