1

順列内の実行を単一の数値にマッピングできるだけでなく、後続の数値を削減できるアルゴリズムが必要です。

したがって、実行は、並べ替えられ、順序どおりに並べ替えられた一連の数値です。リスト 1;2;3;5;6;4 には、1;2;3 と 5;6 の 2 つの実行があります。これらを最小の単一の数値に置き換えたいので、ランを削除した後、4 つの要素の順列がある場合、順列は数値 1 ... 4 を使用します。上記では、2 つのランを減らす必要があります。 . 最初の実行は 1、4 は 2 に変換、[5;6] は 3 に変換され、2 番目の基準を保持します。削減された順列を並べ替えてから、マッピングから内部の要素を展開し、元の順列を並べ替えると、同じ結果が得られます。結果の順列には、ランが含まれていてはなりません。

例（実行を強調表示しました）：

(1;2;3;4;5;6) => 1 //Mappings: 1->1;2;3;4;5;6
(2;3;4);1;(5;6) => 2 1 3 // Mappings: 2->2;3;4, and 3->5;6
(3;4);(1;2);(5;6) => 2 1 3 // Mappings: 2->3;4, and 1->1;2 and 3->5;6

今のところ、リストを渡してリストのリストを作成し、実行をグループ化しています。実際、2 番目の部分は、クリーンなソリューションを作成するのが難しい部分です。私は素朴なアプローチを考えました.誰かが私のものよりもうまくできる巧妙なトリックを持っているかどうかに興味があります.私はO(2n + n log n)のようです.

  • run を run の head 要素に置き換え、そのデータをハッシュテーブルに挿入する (回復可能性のため)
  • ソートされたインデックスを使用して欠落している数字へのマップを作成するためのソート。[1;6;5;4] は [(1,1);(4,2);(5,3);(6,4)] を出力します
  • ステップ 1 のリストをステップ 2 で作成したマップに置き換え、変換のためにハッシュテーブルを更新します。

例をもう一度実行します。

ステップ 1: run を run の head 要素に置き換え、ハッシュ テーブルにデータを挿入する  
    [1;3;4;2;5;6;] -> [1;3;2;5]  
ステップ 2: 配列を並べ替えてマップを作成する  
    [1235]、したがって、前の配列では、1 が 1 に、2 が 2 に、3 が 3 に、4 が 5 にマップされることがわかります。  
ステップ 3: ステップ 1 の配列に対して上記の変換を行います。
    [1;3;2;4]

この順列を並べ替えて再構築すると、[1;2;3;4]、3->3;4、4->5;6、1;2;3;4;5;6 となります。また、ソートされます。

私はリストを使用しているので、機能的なアプローチが好まれます。コードは必要ありません。もちろん、すべてのアイデアを歓迎します。

編集：

次のように:

マッピングの正確な条件が何であるかは明確ではありません。N 回の実行による順列の順列 [1,2,...,N] の生成が許可されないのはなぜですか? 実行をその実行の数値にマッピングすることを好むようですが、(これが常に可能であるとは限らないため) ある程度の自由を許可しているようです。–

run をその run 内の番号にマップすることは好みませんが (上記を参照してください!)、順序を保持する必要があります。順列 [1;2;3...N]はランであるため、さらに削減できます。それが無効である理由です。順序は別のアルゴリズムの後続の操作で重要になりますが、個々の要素を最後に展開して、元の順列を救うことができます。

4

2 に答える 2

2

表記：

  • カウントは1から始まります
  • l.iiリストの要素ですl
  • l+mはリストの連結でlあり、m
  • [n,n+1,n+2,...,m]実行は、いくつかのリストである最大のサブリストでnありm、n <= m

したがってp、リストの順列が与えられます[1,2,...,N]。となるようpにランに分割します。次に、そのような thatの順列を探します。r_1,r_2,...,r_Mp = r_1+r_2+...+r_Mq[1,2,...,M]r_(q.1)+r_(q.2)+...+r_(q.M) = [1,2,...,N]

たとえば、p = [1,3,4,2,5,6]、、、、およびがあります。この場合、 のようにする必要があります。N=6M=4r_1 = [1]r_2 = [3,4]r_3 = [2]r_4 = [5,6]q[1,3,2,4]r_1+r_3+r_2+r_4 = [1]+[2]+[3,4]+[5,6] = [1,2,3,4,5,6]

q定義ごとに 1 を超える長さのランを含めることはできないことに注意してください。もしそうなら、i < Mwith がq.i + 1 = q.(i+1)あり、したがって のサブリストr_(q.i)+r_(q.(i+1)) = r_(q.i)+r_(q.i + 1)があります[1,2,...,N]が、それと矛盾r_(q.i)+r_(q.i + 1)するサブリストでもあり、実行されます。pr_(q.i)r_(q.i + 1)

qここで、与えられた aを見つけるために、数値の挿入と検索、および追加と前方走査を伴うリストをp備えたマッピング データ構造が利用可能であると仮定します。次に、次のことを行います。O(1)O(1)

  • 最初に list を構築しますrunheads = [r_1.1,r_2.1,...,r_M.1]。pこれは、現在の実行を維持しながらトラバースすることで簡単に実行できます。このステップでは、最後に取得するために遭遇した最大数も記憶し、 as キーの要素を使用しNてマッピングを構築します。このステップは明らかに. の値が何であるかは関係ないことに注意してください。そのため、 runを key の値として使用できます。headsrunheadsO(n)headsr_ir_i.1

  • 次に、値を初期値で維持する1まで (およびそれを含めて)反復します。各値について、が にあるかどうかを確認します。この場合、マッピングに追加してを増やします。このステップも明らかに。からに戻ることができるようにするために、追加のマッピングを保存することもできます。Nk1iiheadsi -> kfkO(n)qprevk -> ik -> runheads(i)

  • 最後に、 getfの要素にマッピングを適用します。再び。runheadsqO(n)

例で説明するために、p = [1,3,4,2,5,6].

  • 最初のステップでrunheads = [1,3,2,5]、N=6およびを取得しheads = { 1 -> [1], 3 -> [3,4], 2 -> [2], 5 -> [5,6] }ます。

  • 2 番目のステップでは、何かをしなければならない 4 つのケースがあります: 1、2、3および5。これらのケースでは、それぞれ、、およびの値kがあります。これは、になることを意味します。(保存するものに応じて、またはになります。)1234f{ 1 -> 1, 2 -> 2, 3 -> 3, 5 -> 4 }rev{ 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 5 }{ 1 -> [1], 2 -> [2], 3 -> [3,4], 4 -> [5,6] }

  • を取得するには、どちらが であるかqを計算します。map(f,runheads)[f(1),f(3),f(2),f(5)][1,3,2,4]

したがって、私が間違いを犯しておらず、データ構造が上記の要件を満たしている場合、このソリューションはO(n). O(n*log(n))実際には、独自の ( ) ソリューションを使用する方が実際にはより便利な場合があることに注意してください。規模は大きいpが、数回しか実行していない場合は、それを並べ替えrunheadsて使用してマッピングを作成する方が効率的かもしれません。pこれが事実であるためには、それはかなり大きくなければならないと思います。

于 2009-01-26T23:17:45.383 に答える
0

明確化のために編集

ステップ 1: アルゴリズムを実行しますが、ハッシュ テーブルを 1 つだけ生成する代わりに、マッピング先のセットのヘッドによってインデックス付けされたハッシュ テーブル (D1) を生成します (たとえば、[3,4] の場合は 3 になります)。 (L1) セット自体と

[3;4;6;8;1;2]:

   D1              L1

3 -> [3,4]     1 -> [3,4]

6 -> [6]       2 -> [6]

8 -> [8]       3 -> [8]

1 -> [1,2]     4 -> [1,2]

ステップ 2: 今持っているコレクションを見ると、特定のセットについて、(L1 で) それを見つけたインデックスと Head 値があることがわかります。正しいマップ値は、まだ取得されていないそれらの間の最小整数になります。たとえば、[3,4] の場合、値は 1 から 3 の間でなければならず、1 は既に取得されているため、対応する値は 2 です。値、対応するセットが存在する場合は、より低い値が常に使用されます。この例では、[1,2] が 1 にマップされているため、このキーは既に "取得" されています。したがって、擬似コードでは次のようになります。

for (int Current = 1; Current  < L1.Length; Current++)
{
  GetHead(L1[Current]);
  Index = Current;
  While Head > Index
  {
    if D1.Empty(Index)
    {
      D1.Add(Index,D2[Current])
      D1.DeleteIfNotEmpty(Head);
    }
    else
      Index++;
  }
}

例えば

  • L1 の最初の値を取得します -> [3,4]...
  • 頭を取得 = 3
  • 1 から始めて、既に取得されている D1[1] を検索するため、2 にインクリメントします。
  • 空の D1[2] を探すので、D1[2] = [3,4] を割り当て、D[3] を削除します。

それはO(n)を提供しませんが、O(n+log(n))のようなものを提供します(最初のステップではn、2番目のステップではlog(n))

上記の例では、次のようになります。

1 -> [1,2]
2 -> [3,4]
3 -> [6]
4 -> [8]

[3;4;8;6;1;2] がある場合、結果は次のようになります。

1 -> [1,2]
2 -> [3,4]
3 -> [8]
4 -> [6]

元の配列で絶対順序付けを使用しているため、それで問題ないかどうか、または 6 をインデックス 3 に、8 をインデックス 4 に配置する必要があるかどうかはわかりません。その場合、おそらく L1 を事前注文する必要があります。複雑さを Log(n) だけインクリメントする頭に基づいて

事前注文する必要がある場合は、0(n+log^2(n)) になりますが、これはそれほど悪くはありません (QuickSort が O(Log n) であると仮定すると、L1 は O(log(log n)) になります)

于 2009-01-26T18:45:07.993 に答える