9

事前に入力された単一の配列で動作し、1種類の書き込み操作のみを実行するように制限されている並べ替えアルゴリズムが必要です。

O =アイテムXをインデックスYに移動します。後続の位置の要素は1位置シフトされます。

アルゴリズムは、可能な限り少ない操作数に合わせて最適化する必要がありますO。読み取り操作は、書き込み操作よりも無限に安価です。一時的なヘルパーリストも安いです。

編集：実装は私には隠されていますが、その動作のために、リンクリストと呼ぶ方が正しいかもしれません。

バックグラウンド：

問題は、リストでこの操作を実行することしかできないGoogleAPIに取り組んでいることです。操作はWebサービス呼び出しです。通話回数を最小限に抑えたい。ソートプログラム（クライアント）が開始する前にメモリ内にリストのコピーを持っていると想定できるため、サービスに対して読み取り操作を実行する必要はなく、書き込みのみを実行します。もちろん、リストの複製や既存の.NETソート関数の使用など、サービス呼び出しを実行する前に、ローカルで任意の量の一時的なリストアクションを実行することもできます。

ここでどのように進めますか？ここで使用できる既知のアルゴリズムはありますか？

失敗した試行：

私はすでにダムアルゴリズムを実装しましたが、すべての場合に最適というわけではありません。リストが次のような場合にうまく機能します。

リストA=[2,3,4,5,6,7,8,9,1]

こんなふうになります：

  1. リストはソートされていますか？いいえ
  2. 位置0に属する要素を検索： "1"
  3. 要素「1」を位置0に移動します
  4. （新しいリストの状態A1 [1,2,3,4,5,6,7,8,9]:)
  5. リストはソートされていますか？はい。終わり

...しかし、リストがこのような場合、私はトラブルに巻き込まれます：

リストB=[9,1,2,3,4,5,6,7,8]

  1. リストはソートされていますか？いいえ
  2. 位置0に属する要素を検索： "1"
  3. 要素「1」を位置0に移動します
  4. （新しいリストの状態B1 [1,9,2,3,4,5,6,7,8]:)
  5. リストはソートされていますか？いいえ
  6. 位置1：「2」に属する要素を検索します
  7. 要素「2」を位置1に移動します
  8. （新しいリストの状態B2 [1,2,9,3,4,5,6,7,8]:)
  9. ...あなたは私がここに行くところを見ることができます...
4

3 に答える 3

9

配列の最長増加サブシーケンスを計算します。シーケンスに存在しない各要素に対して書き込み操作を実行します。

編集:例を追加する

入力配列の数値を とします1 3 2 7 4 8 6 5 9。最長の増加シーケンスは1 2 4 6 9です。このシーケンスを計算するときは、シーケンスで発生する要素のインデックスを格納します。次に、元の配列をたどって、シーケンスに存在しない要素を見つけるのは簡単です。この場合、それらは3 7 8 5. これらの各要素に対して、適切な位置に配置する書き込み操作を実行します。したがって、配列の一連の変更は次のようになります。

1 2 3 7 4 8 6 5 9 (after writing 3 to appropriate position)
1 2 3 4 8 6 7 5 9 (after writing 7 to appropriate position)
1 2 3 4 6 7 5 8 9 (after writing 8 to appropriate position)
1 2 3 4 5 6 7 8 9 (after writing 5 to appropriate position)
于 2012-10-05T15:17:06.840 に答える
2

ソートされた最長のサブシーケンスを検索し、ソートされていない各要素を正しい位置にシフトします。

あなたの例のために：

start: 2,3,4,5,6,7,8,9,1 (O = 0)
LSS:   2,3,4,5,6,7,8,9
step:  1,2,3,4,5,6,7,8,9 (O = 1)

start: 9,1,2,3,4,5,6,7,8 (O = 0)
LSS:   1,2,3,4,5,6,7,8
step:  1,2,3,4,5,6,7,8,9 (O = 1)

私の1つ：

start: 9,3,1,7,2,8,5,6,4 (O = 0)
LSS:   1,2,5,6
step:  3,1,7,2,8,5,6,9,4 (O = 1)
LSS:   1,2,5,6,9
step:  1,7,2,3,8,5,6,9,4 (O = 2)
LSS:   1,2,3,5,6,9
step:  1,2,3,8,5,6,7,9,4 (O = 3)
LSS:   1,2,3,5,6,7,9
step:  1,2,3,5,6,7,8,9,4 (O = 4)
LSS:   1,2,3,5,6,7,8,9
step:  1,2,3,4,5,6,7,8,9 (O = 5)

LSS を識別するアルゴリズムが必要です。一度だけ使用する必要があり、取得したら、並べ替え時に要素を挿入するだけです。

擬似コード:

function O(oldindex, newindex):
    # removes oldindex from list, shifts elements, inserts at newindex

function lss(list):
    # identifies the LSS of a list and returns it in a cheap temporary list

function insert(index, element, list):
    # inserts specified specified element into specified index in specified list
    # elements at and after specified index are shifted down to make room

function sort(input):
    lss_temp_list = lss(input)                     # get lss of input list

    do until lss == input:
    old = any(index where (input[index] not in lss)# item in input; not in lss

                                                   # getting new index is uglier
    nl = min(X where (X > input[old] and X in lss))# next lowest element in lss
    nh = max(X where (X < input[old] and X in lss))# next highest element in lss

    new = any(index                                # index of next lowest/highest
          where ((input[index + 1] == nl and nl exists)
              or (input[index + 1] == nh and nh exists))

    O(old, new)                                    # list shift

    il = min(index where (lss[index] > input[new]))# index of next lowest in lss
    ih = max(index where (lss[index] < input[new]))# index of next highest in lss
    i = any(X where (X == il or X == (ih + 1)))    # index to insert element
    insert(i, input[new], lss)                     # add new element to lss
    repeat
    return input

不安定な疑似コード スタイルで申し訳ありません。コード ブロックにスクロール バーが必要にならないように、コードを十分に狭くしようとしていました。

于 2012-10-05T16:48:30.530 に答える
2

配列をローカルに並べ替えます。オリジナルのコピーを保管してください。

LCS distanceを使用して、元の配列と並べ替えられたバージョンの間の最適な編集シーケンスを計算します。これは、置換が許可されていないレーベンシュタイン距離の変形です。レーベンシュタインの動的計画法アルゴリズムの簡易バージョンを使用して、LCS 距離を計算できます。プログラムのソース コードをdiff調べて、動的プログラミング テーブルから編集シーケンスを取得する方法を確認します。

これで、元の配列をソート済みバージョンに変換するために実行する挿入と削除のリストを意味する編集シーケンスができました。挿入を実行します。(削除は操作 O によって実行されるため、スキップできますが、そのために配列へのインデックスが変更されることに注意してください。そのため、それを補正する必要があります。)

于 2012-10-05T15:13:30.870 に答える