面白いアナグラムを見つける

Question

$ a_1a_2 ldots a_n $ and $ b_1b_2 ldots b_n $は同じ長さの2つの文字列であると言います。 an アナグリン 2つの文字列は、$ i $ごとに$ a_i = b_ {p（i）} $であるように、$ p：[1 ldots n] to [1 ldots n] $をマッピングする生物多様なマッピングです。

同じ文字列には複数のアナグルがあるかもしれません。たとえば、$ a = $ `abcab`および$ b = $の場合cabab $ p_1 [1,2,3,4,5] to [4,5,1,2,3] $および$ p_2 [1,2,3,4,5] to [2,5、 1,4,3] $など。

私たちはそれを言います 重さ $ w（p）$の$ $ $ p $は、2番目の文字列を取得するために再配置できるチャンクを取得するために最初の文字列に作成する必要があるカットの数です。正式には、これは$ p（i）+1 ne p（i+1）$の$ i in [1 ldots n-1] $の値の数です。つまり、それは$ P $が行うポイントの数です いいえ 正確に1.たとえば、$ w（p_1）= 1 $ and $ w（p_2）= 4 $、$ p_1 $ cotsは 12345 一度、チャンクに 123 と 45, 、および$ p_2 $ cuts 12345 4回、5つのチャンクに。

2つの文字列$ a $と$ b $のアナグルが存在するとします。その後、少なくとも1つのアナグラムの重みが最小になる必要があります。これがそうだとしましょう 最も軽い. 。 （最も軽いアナグラミングが複数あるかもしれません。私はウェイトだけに興味があるので気にしません。）

質問

アナグラムが存在する2つの文字列が与えられたアルゴリズムが必要です。 最も軽いアナグルの正確な重量を生成します 2つの文字列の。アルゴリズムが最も軽いアナグラムを生成する場合は大丈夫ですが、必要はありません。

すべてのanagrammingsを生成して重量を量るのはかなり簡単な問題ですが、多くの場合があるかもしれませんので、明るいanagrammingsを直接見つける方法を好むでしょう。

---

動機

この問題が興味深い理由は次のとおりです。コンピューターに辞書を検索し、まったく同じ文字を含むアナグラム、ペアのペアを見つけるのは非常に簡単です。しかし、作成されたアナグラムの多くは興味がありません。たとえば、Websterの2番目の国際辞書にある最も長い例は次のとおりです。

胆嚢植物腫瘍術
duodenocholecystostomy

問題は明確でなければなりません。これらは、単に交換する非常に軽いアナグラムを認めているため、面白くありません。 cholecysto, duedeno, 、 と stomy 一方、2の重量のセクションは、このはるかに短い例です。

海岸線
断面

ここでは、最も軽いアナグラムの重み8です。

この方法を使用して興味深いアナグラムを見つけるプログラム、すなわちすべてのアナグラミングが重量であるプログラムがあります。しかし、これは、可能なすべてのアナグラミングを生成し、計量することによって行われますが、これは遅いです。

Answer 1

この問題は、「最小コモンストリングパーティション問題」として知られています。 （より正確には、最小コモンストリングパーティションの問題の答えは、問題の答えに等しく、1。）残念ながら、各文字が各入力文字列で最大2回発生するという制限があるとしても、それはNPハードです。 Goldstein、Kilman、およびZheng [GKZ05]によって証明されています。これは、p = npでない限り、多項式時間アルゴリズムが存在しないことを意味します。 （もちろん、各文字がせいぜい1回発生した場合、1つのアナグル化しかないため、問題は些細なことです。）

正の面では、同じ著者[GKZ05]は、同じ制限の下で多項式時間1.1037承認アルゴリズムを与えます。 （「1.1037-近似アルゴリズム」は、正解を出力しない可能性のあるアルゴリズムを意味します a しかし、値を出力することが保証されています b そのような a ≤ b ≤ 1.1037a。）また、各文字が各入力文字列で最大3回発生するという弱い制限の下で、線形時間4承認アルゴリズムを与えます。

GKZ05] Avraham Goldstein、Petr Kolman、およびJie Zheng。最小コモンストリングパーティションの問題：硬度と近似。 Combinatoricsの電子ジャーナル, 、12、記事R50、2005。 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50

Answer 2

これはフォローアップです 上記のtsuyoshi Itoの答え, 、の最も関連性の高い部分を要約します GKZ05ペーパー 彼は引用した。

この論文は、最大の独立したセットが減少することを証明しています（ミス） 問題。頂点がペア$（i、j）$であるグラフ$ g $を作成します。 Vertices $（i、J）$および$（k、 ell）$（ここで$i≤k$）をエッジで接続します。 1 mapsto J+1 $および$ k mapsto ell $および$ k+1 mapsto ell+1 $。これは簡単に検出できます。このようなマッピングは、次のいずれかが正確に保持された場合に不可能です。

1. $ i = k $および$ j ne ell $
2. $ i+1 = k $および$ j+1 ne ell $
3. $ i+1

結果のグラフ$ g $には、サイズ$ s $の最大独立したセットがあります。次に、最小アナグリンの重みは正確に$ ns-1 $です。ここで、$ n $は文字列$ a $ a $と$ b $の長さです。 （コンバースも保持されます：低重量のアナグラムは、$ g $の大きなミスに直接変換されます。詳細については、ペーパーの4〜5ページを参照してください。）

たとえば、2つの文字列を検討してください yttrious と touristy. 。対応するグラフには2つの頂点があります。1つは共有用です ou ペアと共有用の1つ ri ペア。両方をマッピングするアナグルミングを持つことが可能であるため、頂点の間にエッジはありません。 ou に ou と ri に ri;または、何よりも3つの条件が失敗することを確認できます。したがって、グラフは明らかにサイズ$ s = 2 $のMISを持ち、最小アナグルの重みは実際に8-2-1 = 5で、アナグラムに対応しています y|t|t|ri|ou|s ↔ t|ou|ri|s|t|y.'

一方、考慮してください derater と treader. 。今回はグラフには3つの頂点があります。

1. DErater + treaDEr
2. dERater + treadER
3. deratER + treadER

2と3は互換性がなく、1と3は互換性がありませんが、1と2は互換性があります。したがって、一意のMISにはサイズ$ s = 2 $があり、頂点1と2が含まれています。 der|a|t|e|r ↔ t|r|e|a|der.

Answer 3

念頭に置いていた正確なアルゴリズムをカバーしていません（これ ツヨシ島の答えはそうです）、しかし、「興味深い」アナグラムを見つけるという根本的な問題を遂げようとしています...

私の最初の考えは、編集距離にいくつかのバリエーションを使用することでした。ここでは、原子の変化は、通常の「難易度」または「混乱性」の重みではなく、「興味深い」に従って重み付けされます。もちろん、このように本当に興味深い変換を効率的にエンコードできる可能性は低いようです。なぜなら、それらは非ローカルである可能性が高いため、MISのNP完全な問題に遭遇する可能性が高いからです。

したがって、2番目の考えは、単語間の文字から文字へのアラインメントを構築し（マシン変換アラインメント）、「興味深い」のためにアラインメント自体をスコアリングすることです（例えば、隣接する文字を非隣接するアラインメントをカウントします。隣接する文字、または各アライメントが交差するアラインメントの数など。そして、それらをすべてlogLinearモデルなどを介して結合します）。

3番目のアイデアは、アナグラム自体の構造を完全に見捨て、代わりに単語のセマンティクスを見ることです。多くの場合、アナグラムを「興味深い」ものにしているのは、関係する言葉の意味の間の不一致です。したがって、WordNetなどで距離を計算するなどのことを試してみてください。

Answer 4

問題は、その観点から表現できます 順列グループ.

ここで、順列グループには、すべての「アナグラムの動き」が含まれています。プリミティブ（2文字を交換）と一連のプリミティブ移動シーケンスの複合です。可能な順列のサブセットのみに興味があるようです。これらを定義しようとします。

まず、順列の表記、すなわちいわゆるものを思い出してください サイクル表記:

• $（）$は順列を意味しません。
• $（1）は、1が1で交換されることを意味しますが、これも順列ではありません。
• $（12）$は1と2が交換されることを意味します。
• $（123）$は、1を置き換える2を置き換える1を意味します。
• そして、1つ

これらの単純な「サイクル」は、より複雑な順序を記述するために構成されています。

あなたが興味を持っている動きは（$ n $の長さのために）です。

• 単一文字のペアのスワップ：これらは$（12）$などのスワップです
• 2つの連続した文字のペアのスワップ：これらはフォーム$（a b）（a+1 b+1）$の順列です。ここで$ a> 0 $および$ b
• ...
• n連続した文字のペアのスワップ：これらはフォーム$（a b）（a+1 b+1） cdots（a+i-1 b+i-1）$のフォームの順列です$ a> 0 $、$ a+i-1 le b $、および$ b+i-1 le n $。

これらの動きは、アルゴリズムの基礎を形成します。あなたが興味を持っているのは、これらの動きの最小シーケンスを見つけて、ある単語から次の単語に移動することです。

ブルートフォースの検索とは別に、これを計算するためのアルゴリズムはわかりませんが、少なくとも今では、原始的な動きが何であるかについてより明確な（私が望む）説明があります。 （そして、おそらく私たちの中のいくつかのグループ理論家は、適切なアルゴリズムを指すことができます。）

Answer 5

胆嚢星duodeodenostomy/duodenocholecystostomeの場合、各キャラクターに数字を割り当てた場合、それがデルタとしてどれだけ移動したかを説明する場合、7 7、次に8-7、6 0のようなものがあることに気付きます。一部のcharが繰り返された可能性があるため、それは正しくありません（2番目のCは前方に移動し、7ではなく前方に移動しました）など、同じデルタを連続して見えるため、実行される長さをエンコードできます」。

（+2）（+5）（+5）（ - 3）（ - 1）（+3）のようなものが表示される海岸線/断面と比較してください。

おそらく、デルタのランダム性は、アナグラムがどれほど面白いかについて「スコア」を与えることができますか？