4

最近、指定した回数だけ文字列を複製する必要がありました。文字列 " " のコピーが 5 つ必要で、エディターbaconに " " が 1 行あるとします。baconだから私はこれから始めます：

bacon

そしてこれで終わります：

bacon
bacon
bacon
bacon
bacon

コピー、貼り付け、削除という 3 つの「アトミック」操作も定義しましょう。「コピー」では任意の数の行をコピーできます。「貼り付け」では最後にコピーしたものを貼り付け、「削除」では行を削除します。したがって、3 行の " bacon" がある場合:

bacon
bacon
bacon

そして、10 行の " bacon," が必要です。次のようなことができます。

copy 2  | lines of bacon: 3
paste 2 | lines of bacon: 5
copy 5  | lines of bacon: 5
paste 5 | lines of bacon: 10

しかし、 i行とj行 ( i ≤ j )が与えられた場合、必要な「アトミック」操作の最小数はいくつになるでしょうか? この問題に適用されるアルゴリズム手法はありますか? それとも、明らかな何かを見落としていますか？

4

3 に答える 3

3

シーケンスの削除とそれに続く貼り付けについて考えてみます。これにより、貼り付けの後に削除が続くのと同じ状態になることに注意してください。したがって、これらの操作は前後に入れ替えることができます。

次に、シーケンスの削除とそれに続く「コピーN」について考えます。これは、「コピーN」の後に削除が続くのと同じ状態になるため、これらのシーケンスを交換できることに注意してください（ただし、一方向のみ）。

したがって、どの一連の操作でも、最終結果を変更せずに、削除をそれに続く操作と交換できます。したがって、結果を変更せずに、すべての削除操作を最後に移動できます。

このことから、削除が最適な順序で表示された場合、それらを順序の最後に移動できることになります。

XXXXXXXXDDDD

（XはCまたはPのいずれかです）

ただし、後続の貼り付けなしでコピーを作成するのは最適ではないため、シーケンスは実際には次のようになります。

XXXXXXPDDDD

ここで、貼り付け+削除（PD）シーケンスを、コピー+貼り付け（CP）シーケンスに置き換えることができることに注意してください。この場合、コピーは1行少なくなります。これにより、2つの操作が他の2つの操作に置き換えられるため、何も失われません。したがって、最適なシーケンスを次のように変換できます。

XXXXXXCPDDD

そして、すべての削除を削除するために、もう一度3回実行できます。

XXXXXXCCCCP

もちろん、コピーのシーケンスは最適ではないため、答えは次のようになります。

XXXXXXCP

つまり、最適なシーケンスの一部として削除が必要になることはありません。

コピー+貼り付け+コピー+貼り付けでいつでも置き換えることができるため、4つの貼り付けを連続して行う必要はありません。（ただし、連続して3つのペーストが必要になる場合があります。たとえば、4から13になります）

そして、それは私が今のところ得ている限りです。この時点で、ダイクストラスタイルの幅優先探索を実行して最短経路を探すことができます...

[アップデート]

Mark Petersがコメントで指摘しているように、3回続けて貼り付ける必要もありません。証拠：

Copy（N）では、Nが行数よりも小さい必要があります。したがって、コピー（N）+貼り付け+貼り付け+貼り付けは、常にコピー（N）+貼り付け+コピー（2N）+貼り付けに置き換えることができます。

したがって、最適なシーケンスは、削除なし、行に2つのコピーなし、および行に2つ以下の貼り付けなしで形成できます。さて、それは始まりです。

于 2012-05-01T04:17:10.973 に答える
2

探しているシーケンスを正規化しましょう。これは、ネモの答えのように始まります。

  1. 有効なシーケンスは、D*(C[DP]*)* によって一致します。DC(n) → C(n) D と DP(n) → P(n) D に書き換えます。

  2. 有効なシーケンスは (CP*)*D* によって一致します。C(n) D → D および P(n) D → C(n-1) P(n-1) と書き換えます。時間の関数としてのバッファ長は単峰性であるため、新しいコピーは問題ありません。

  3. 有効なシーケンスは (CP*)*|D* によって一致します。

i ≤ j なので、探しているシーケンスは (CP*)* に一致します。

  1. 有効なシーケンスは (CP*)* によって一致します。書き換え C(n) P(n) P(n) P(n) P(n) P(n) → C(n) P(n) C(2n) P(2n) P(2n) C(n) .

  2. 有効なシーケンスは (CP{0,4})* によって一致します。C(n) C(n') → C(n') と書き換えます。

  3. 有効なシーケンスは (CP{1,4})* で一致します。C(n) P(n) P(n) P(n) P(n) → C(n) P(n) P(n) C(2n) P(2n) と書き換えます。次のコマンドが存在する場合はコピーであるため、コピーを復元する必要はありません。

  4. 有効なシーケンスは (CP{1,3})* によって一致します。C(n) P(n) P(n) P(n) → C(n) P(n) C(2n) P(2n) と書き換えます。コピーを復元する必要はありません。

探しているシーケンスは (CP{1,2})* と一致します。2(n) = C(n) P(n) および 3(n) = C(n) P(n) P(n) と省略します。バッファ全体をコピーする場合は全体コピーを呼び出し、そうでない場合は部分コピーを呼び出します。1行を除いてバッファ全体をコピーする場合、コピーをほぼ全体と呼びます。コマンドに注釈を付けるために w と p と a を使用します。

部分コピーの削減に取り組みましょう。2p(n) … 2?(n') があるとします。2w(n+δ) … 2p(n'-δ) または 2w(n+n') … に書き換えて、部分コピーの数を減らすことができます。3p(n) … 3?(n') についても同じことができます。最適性を仮定すると、3p(n) … 2?(n') を実行できます。3p(n+δ) … 2p(1) に固執することはできません。なぜなら、3?(n+δ+1) … D は同等で短いからです。2p(n) … 3?(n') のようなことはできますが、最終的には 2 はほとんど完全なものにすぎない可能性があります。

この書き換えは、常に左端の部分コピーをメイトで処理する場合に収束します。さらに 2w(n) 3w(2n) → 3w(n) 2w(3n) と 2w(n) 2w(2n) 2w(4n) 2w(8n) → 2w(n) 3w(2n) 3p(5n) 、有効なシーケンスは 2w{0,3} 3w* ( | 2p | 2a? 3w* 3p ) によって一致します。

log(n)時間アルゴリズム

明らかに、最適解の長さは O(log(n)) です。上記の正規表現に一致する各ソリューションの 3w コマンド数の下限と上限を計算できます。これらの境界は一様定数だけ異なります。O(log(n)) が存在する、もっともらしいコマンドの短いシーケンスをすべて試してください。多くても 1 つのコピー量が指定されていません。パターンが機能する場合にどうあるべきかを計算するのは簡単です。

于 2012-05-01T14:57:34.753 に答える
2

コピー＋ペーストの2回の操作で最大2倍の行数が可能です。オペレーションとサイズの比率は 2:2 です。2 回続けて実行すると、4 回の操作で 4x が得られます。

コピー＋ペースト＋ペーストの3つの操作で、最大3倍の行数を実現。オペレーションとラインの比率は従来と同じ3:3。しかし、2 回続けて実行すると、6 回の操作で 9 倍になり、改善されます。

コピー＋ペースト＋ペースト＋ペーストの4つの操作で、行数を4倍にすることができます。比率は4:4で同じです。2 回続けて実行すると、8 回の操作で 16 倍になります。

5 つの操作、コピー + 4*貼り付けで、行数を 5 倍にすることができます。しかし、2 つと 3 つの操作シーケンスを組み合わせると、同じ数の操作で行数を 6 倍にすることができます。これらを外挿すると、2、3、および 4 つの操作シーケンスの組み合わせに勝るものはないことがわかります。

私のアドバイスは、結果が目標の 4 倍以内になるまで 4 つの操作シーケンスを使用し、その後、3 つまたは 2 つの操作シーケンスに切り替えて終了することです。

于 2012-05-01T04:08:22.793 に答える