研究成果 > アルゴリズムのデモ > 共有区間列挙問題

共有区間列挙問題とは

与えられた二つの順列を比べて,部分的に似ている場所を探す問題を考えて見ます.たとえば,

順列 A 1 2 3 4 5
順列 B 2 4 3 5 1

に対しては,

   順列 A のうち 3 4 の部分は順列 B の 4 3 の部分
と(並び方を無視すれば)一致しています. この他にも連続している部分(これを区間と呼びます)で一致している場所としては,
  順列 A の 2 3 4 の区間と順列 B の 2 4 3 の区間
があります.このような,中身の要素が一致している区間の対を「共有区間」と呼びます.

一般に,n個の要素からなる順列が 2本与えられたとき,共有区間をすべて列挙する問題を考えます.ただし, 長さ(区間に含まれる要素数)が 2以上 n-2 以下のものだけを考えます(理由は下の注釈1参照). 順列対に 対する基礎的な問題です. 先の順列 A,B に対しては

(2 3 4) と (2 4 3)
(3 4) と (4 3)
(3 4 5) と (4 3 5)
が列挙するべき区間対です.

単純な方法で列挙しても n が小さければ実用的ですが,n が大きいときには工夫が必要です. アルゴリズムを うまく工夫すると,n が1000万と巨大になっても,あっという間に列挙することが出来ます.

デモの説明

要素数 n=10 の問題例に対して,共有区間を計算して列挙します. 二つの順列 A と B は「問題例」に表示さ れています(A は常に 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ですが B は自由に変更できます).順列 A, B に対し て計算された共有区間が「答え」の下に表示されます.共有区間の部分は赤く色が塗られます.

遊び方

「ランダムに問題を生成して計算する」をクリックすると,順列 Bをランダムに生成して計算を行い,答えの下 に結果を表示します.順列 Bの数字の横のV字ボタンをクリックして,現れた数字をクリックして選択すること で,順列 Bの数字を適当に変えてみることが可能です. ただし,順列であることを保つため,一部を修正する と順列B の他の数字も連動して変化します. (Q: 順列B をうまく定めて,列挙すべき共有区間をなしにする ことができるでしょうか?)

「計算する」をクリックすると,現在表示されている順列対に対して計算を行い,答えの下に結果を表示します.

「元に戻す」をクリックすると,初期状態あるいは「ランダムに問題を生成して計算する」を最後にクリッ クしたときに生成された順列まで戻ります.

なお,順列 A は

1 2 3 4 5 6 7 8 9 10
に固定しても一般性を失わないので固定しています(注釈2参照).

注釈1: 長さ1, n-1, n の共有区間を考えない理由

長さ 1 のものと長さ n のものは必ず共有区間になります.また,長さ n-1 のものは簡単に存在を確認できま す. たとえば,最初の例

順列 A 1 2 3 4 5
順列 B 2 4 3 5 1
に対して
(2 3 4 5) と (2 4 3 5)
は長さ n-1 の共有区間ですが,順列 A の先頭の要素 1 が順列 B の最後にあることから,共有区間になること がすぐに分かります. このように,二つの順列の(ア)先頭同士,(イ)末尾同士,(ウ)先頭と末尾,のい ずれかの組合せに同じ要素があるかどうかを調べるだけで長さn-1 の共有区間の存在は確認できます. よって, これらは自明なものと考え,考察の対象から外すことにします.

注釈2: 順列 A を固定してもよい理由

名前をつけ変えて順列 A が(1 2 3 ... n)となるようにしても問題の本質は変わらないからです. 数字は単 なるラベルであって,その大小が問題に影響を与えないことが分かればこれはすぐに理解できるでしょう. た とえば,

順列 A 3 1 2 5 4
順列 B 2 4 3 5 1

の数字を 1 → a, 2 → b, 3 → c, 4 → d, 5 → e と書き換えて

順列 A c a b e d
順列 B b d c e a

としても等価な問題です. この問題を解いた結果に対してラベルをもとに戻せば(たとえば a → 1) もとの問題の答えが得られるからです. 同じように,数字を 1 → 2, 2 → 3, 3 → 1, 4 → 5, 5 → 4 と書き換えて

順列 A 1 2 3 4 5
順列 B 3 5 1 4 2

としても等価な問題になるのです.