24

次の質問が突然関連しているように見えたとき、私はプログラミングの質問を調べていました。

次のように少ないスワップを使用して、文字列を別の文字列に変換するにはどうすればよいですか。文字列は相互変換可能であることが保証されています (同じ文字セットを持っています。これは指定されています)が、文字は繰り返すことができます。文字が繰り返されることなく、同じ質問でウェブの結果を見ました。文字列内の任意の 2 文字を入れ替えることができます。

たとえば、「aabbccdd」は 2 回のスワップで「ddbbccaa」に変換でき、「abcc」は 1 回のスワップで「accb」に変換できます。

ありがとう！

4

3 に答える 3

8

これは、 Subhasis の回答の拡張および修正版です。

正式には、問題は、n文字のアルファベットVと 2 つの m文字の単語xとyが与えられ、 p ( x ) = yとなるような順列pが存在する場合、スワップの最小数 (修正する順列) を決定することです。 2 つの要素を除くすべて) の組成qがq ( x ) = yを満たす。n文字の単語が集合 {1, ..., m } からVへの写像であり、pおよびqであると仮定すると、は {1, ..., m } の順列であり、アクションp ( x ) は合成pの後にxが続くものとして定義されます。

構成がpであるスワップの最小数は、 pのサイクル分解で表すことができます。j 1 , ..., j kが {1, ..., m } で対ごとに異なる場合、サイクル ( j 1 ... j k ) は、 j iを i のj i + 1にマッピングする順列です。 {1, ..., k - 1} は、j kをj 1にマップし、他のすべての要素をそれ自体にマップします。順列pは、すべての異なるサイクル ( j p ( j ) p ( p ( j )) ... j' ) の合成です。ここで、jは任意で、p ( j ') = jです。各要素は構成されたサイクルの 1 つに正確に表示されるため、構成の順序は重要ではありません。k要素サイクル ( j 1 ... j k ) は積 ( j 1 j k ) ( j 1 j k - 1 ) ... ( j 1 k - 1 サイクルのj 2 ) 。一般に、すべての順列は、mスワップの構成からそのサイクル分解を構成するサイクル数を差し引いたものとして記述できます。簡単な帰納法証明は、これが最適であることを示しています。

ここで、Subhasis の回答の核心に迫ります。アスカーの問題のインスタンスは、オイラー(すべての頂点について、入次数は出次数に等しい) ダイグラフGと1対 1で対応します。{1, ..., n } のjの場合、 jというラベルの付いたアークはy ( j ) からx ( j ) に進みます。Gに関する問題は、Gのアークを有向サイクルに分割することができる部分の数を決定することです。( G以来これは、次のように、q ( x ) = yとなる順列qが分割と 1 対 1 で対応しているためです。qの各サイクル ( j 1 ... j k ) には、有向サイクルがj 1、...、j kとラベル付けされたアークで構成される部分があります。

Subhasis の NP 硬さ削減の問題は、オイラー有向グラフでのアーク分離サイクル パッキングは、一般的な有向グラフでのアーク分離サイクル パッキングの特殊なケースであるため、後者の NP 硬さの結果は、前者。しかし、ごく最近の研究(以下の引用を参照) では、実際、オイラーの特殊なケースでさえ NP 困難であることが示されています。したがって、上記の対応により、質問者の問題も同様です。

Subhasis が示唆しているように、この問題は、アルファベットのサイズであるnが固定されている (固定パラメーターで扱いやすい)多項式時間で解決できます。アークがラベル付けされていない場合、識別可能なサイクルがO ( n !) 個あるため、識別可能なサブグラフの数であるサイズO ( m n ) の状態空間で動的計画法を使用できます。実際には、バイナリ アルファベット (としましょう) にはそれで十分かもしれませんが、大きなアルファベットのインスタンスでこの問題を正確に解決しようとすると、線形計画法を使用して境界を取得して、分枝限定を試みる可能性があります。サイクルを部分的にパックするための列生成。

@article{DBLP:journals/corr/GutinJSW14,
  author    = {Gregory Gutin and
               Mark Jones and
               Bin Sheng and
               Magnus Wahlstr{\"o}m},
  title     = {Parameterized Directed \$k\$-Chinese Postman Problem and \$k\$
               Arc-Disjoint Cycles Problem on Euler Digraphs},
  journal   = {CoRR},
  volume    = {abs/1402.2137},
  year      = {2014},
  ee        = {http://arxiv.org/abs/1402.2137},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
于 2014-05-15T20:10:08.197 に答える