問題タブ [dutch-national-flag-problem]

0、1、または 2 を含むリンク リストを並べ替えたいと思っていました。さて、これは明らかにオランダ国旗問題の変種です。 http://en.wikipedia.org/wiki/Dutch_national_flag_problem

リンクに示されているのと同じアルゴリズムは次のとおりです。

「上のグループを配列の上から下に、下のグループを下から上に成長させ、中央のグループを下のすぐ上に保持します。アルゴリズムは、上のグループのすぐ下、下のすぐ上、および3 つのインデックスの真ん中のすぐ上. 各ステップで, 真ん中のすぐ上の要素を調べます. 上のグループに属している場合は, 一番上の要素と交換します. 下のグループに属している場合は, 上の要素と交換します.底のすぐ上にある場合はそのままにしておきます。適切なインデックスを更新します。複雑さは Θ(n) 回の移動と検査です。"

そして、同じために与えられた C++ 実装は次のとおりです。

}

私の唯一の質問は、ここで配列で行っているように、リンクされたリストをどのようにトラバースするかということです。

以下のオランダ国旗ソリューションは、0、1、および 2 の 3 つの要素のみを含む特定の入力配列では機能しないようです。

配列のサイズを小さくすると、うまくいきます。エラーを特定できません。

何か不足していますか？

更新: 上記の同じコードは、より小さいサイズの配列で機能します: http://ideone.com/bgEgCs

少し助けて、みんな。特定のパターンに従ってリストをソートする方法例は、R、W、B のリストをソートすることです。ここで、R が最初に来て、次に W、B のよう(sortf '(W R W B R W B B))になります。(R R W W W B B B)

どんな答えでも大歓迎です。

オランダの国家問題はこの問題です: 私は一連の文字 x^k (k >= 3) を持っています 私の目標は、この文をオランダの国旗に変換することです:

xxx は RWB を与える

xxxx は RWBB を与える

xxxxx は RWWBB を与える

xxxxxx は RRWWBB を与える

...

R <= W <= B <= R+1

1 つのリボンと n.log(n) の複雑さを備えたチューリング マシンを設計したいと考えています。事実、標準アルゴリズムはスワップを使用しており、私はそれを使用できません。これは、この種のチューリング マシンでは利用できません (十分に効率的ではありません) ....

あなたはそれを行う方法を知っていますか？:)

学習課題として、私は C でクイックソート アルゴリズムを実装しています。ピボットは 3 つの値の中央値であり、要素が 4 つ以下のパーティションの場合は、挿入ソートに切り替えます。

現在、2 つのバリアントをテストしています。1 つはHoare の partition schemeを使用し、もう 1 つはDutch Flagを使用しています。

更新:両方の亜種のファイル全体が含まれています。

ホーアの：

オランダ国旗:

どちらも同じ入力、一連のファイルを取得します。各ファイルには10^n、範囲が のランダムな整数値が含まれています[0:(10^n)+1]。n範囲は 1 から 7 (1000 万から 1000 万要素) です。私は、Dutch Flag の実装が少なくとも Hoare のものと同じくらい速いと思っていましたが、そうではありませんでした。

フラグ:-O3

次に、入力を変更しました。同じサイズですが、多くの繰り返し値を保証する10^n値が含まれています。[0:10^(n-1)]

結果：

値が繰り返される場合でも、Dutch Flag は Hoare のものよりも遅いです。なんで？選択されたピボットが一意である可能性は低いようです。

私の環境、それが重要な場合：

2 色と 3 色のソリューションを試しましたが、4 色では解決できません。

助けてください。

でしょうrrbb????yyygggか？緑の旗をどのように交換しますか?

以下の解決策を試しましたが、最後の黄色を緑色に交換してもうまくいきません。

オランダ国旗問題のソルバーを作ろうとしています。基本的には、リストを与えられて、赤白青の順に並べ替えたいと思います。赤、白、青は述語 (つまり、赤 (x)、白 (x) など) によって定義されます。現在、次のコードがあります。

私の出力は次のようになります。

私が欲しいのは、それが次のようになることです：

出力を希望どおりにするためにいくつかの方法を試しましたが、どこにも近づくことができませんでした。

編集:すべての可能なセットを並べ替え、セットが「オランダの旗」の順序であるかどうかを評価するブルート フォース ソリューションを使用して解決できるようです。しかし、より良い解決策はありますか？

3 色の DNF 問題を理解しました。色の数を 5 (0,1,2,3,4) に拡張したいとしますが、それでも O(n) の複雑さを得ることができますか?

したがって、2 が未知の領域である 5 つの領域があると思います。しかし、これを実装する方法は？3 色のアルゴリズムを 5 色に簡単に拡張できますか?