問題タブ [data-partitioning]

「プロダクト パーティション」についての情報を探しています (正式な名前はわかりません)
。「クラシック」パーティションでは、正の整数の分解を合計として検索します。

すべての分解を積として見つけたい:

再帰的な解決策がありますが、十分に効率的ではありません。
情報をお寄せいただきありがとうございます。

Philippe
PS
これが私の解決策です(C#):

---------------------------------------------- (7月10日）
ここに投稿されたさまざまな回答にもかかわらず、私はまだパフォーマンスの問題に悩まされています。
素数が { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 } で、素数の最初の N 個の要素の積に私のバージョンを適用すると、次の結果が得られます。

もっと良いものがあると確信しています。
この機能がすでに研究されていて、どこで情報を見つけることができるかについて、誰も私に答えませんでした.
インターネットで何度か検索してみましたがだめでした…

ご協力いただきありがとうございます。
フィリップ

Lomuto のQSort パーティションの特定のソリューションが安定しているかどうか(Hoare のバージョンが不安定であることはわかっています) を Web とアルゴリズムの本で検索しようとしましたが、正確な答えが見つかりませんでした。
だから私は同じ例を作ろうとしましたが、安定しているようです。しかし、私はそれを示しませんでした。私たちを手伝ってくれますか？安定していない場合は、入力の例を見つけてもらえますか?

LINQ を使用して、C# のシーケンスをシーケンスのシーケンスに分割したいと思います。私はいくつかの調査を行いましたが、わずかに関連していることがわかった最も近い SO 記事はthisです。

ただし、この質問は、定数値に基づいて元のシーケンスを分割する方法を尋ねているだけです。操作に基づいてシーケンスを分割したいと思います。

具体的には、小数プロパティを含むオブジェクトのリストがあります。

のシーケンスがExampleClassあり、対応する の値のシーケンスTheValueは次のとおりです。

元のシーケンスを、似IEnumerable<IEnumerable<ExampleClass>>ている値を持つに分割したいと思います。TheValue

これがどのように実装されるのか、私はただ迷っています。お手伝いできますか？

私は今、非常に醜い解決策を持っていますが、LINQ が私のコードの優雅さを増すという「感覚」を持っています。

ナイーブクイックソートでは、すべてのキーがピボット値の前または後に分割されるため、一意のキーを含まない配列をソートするのにO（n ^ 2）時間がかかります。重複キーを処理する方法があります（クイックソートで説明されているものは最適です）。提案されたソリューションはHoareパーティションに対してのみ機能しますが、私はLomutoパーティションを実装しました。重複キーを処理するために、ピボットの左側に重複を移動することと、ピボットの右側に重複を移動することを交互に行いました。アルゴリズムは次のように機能します。

重複キーを処理するためのより良い（より効率的な）方法はありますか？

編集：私のコード（示されているように）は、compareToがequalsと一致している必要があります（それが要件ではないとしても）

『Introduction to Algorithms』という本のクイックソートの章で説明されているクイックソート アルゴリズムは、Hoare-Partitioning を採用していません。

一般的なホア パーティショニングに対するこのアプローチの利点について、誰か教えてください。それとも作者の好みの問題なのでしょうか？

TCP 経由で次のメッセージを受信して​​います。

しかし、それを分割しようとすると

次の配列を取得しています。

('{\x00\x00\x00"\x00\x00\x00m\x00\x00\x00e\x00\x00\x00s\x00\x00\x00s\x00\x00\x00a\x00\x00\x00g\x00\x00 \x00e\x00\x00\x00"\x00\x00\x00:\x00\x00\x00 \x00\x00\x00"\x00\x00\x00# \x00\x00\x00B\x00\x00\x00E\x00 \x00\x00G\x00\x00\x00I\x00\x00\x00N\x00\x00\x00;\x00\x00 \x00A\x00\x00\x00l\x00\x00\x00l\x00\x00\x00;\x00 \x00\x000\x00\x00\x00;\x00\x00\x001\x00\x00 \x00;\x00\x00\x000\x00\x00\x00;\x00\x00\x001\x00\x00\x003\ x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x000\x00\x00\x006\x00\x00\x00.\x00\x00\x007\x00\x00\x004\ x00\x00\x00.\x00\x00 \x001\x00\x00\x002\x00\x00\x005\x00\x00\x00:\x00\x00\x003\x00\x00\x000\x00\x00\x000\ x00\x00 \x000\x00\x00\x000\x00\x00\x00;\x00\x00\x00#\x00\x00\x00E\x00\x00\x00N\x00\x00\x00D\x00\x00 \x00" \x00\x00\x00,\x00\x00\x00 \x00\x00\x00"\x00\x00\x00c\x00\x00\x00l\x00\x00\x00i\x00\x00 \x00e\x00\x00\x00n\x00\x00\x00t\x00\x00\x00"\x00\x00\x00: \x00\x00\x00 \x00\x00\x00"\x00 \x00\x001\x00\x00\x003\x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x000 \x00\x00\x006 \x00\x00\x00.\x00\x00\x007\x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x002\x00\x00 \x005 \x00\x00\x00"\x00\x00\x00,\x00\x00\x00 \x00\x00\x00"\x00\x00\x00t\x00\x00\x00y\x00 \x00\x00p\x00\x00\ x00e\x00\x00\x00"\x00\x00\x00:\x00\x00\x00 \x00\x00\x002\x00\x00\x000 \x00\x00\x000\x00\x00\x005\x00\x00\ x00}\x00\x00\x00<\x00\x00\x00E\x00\x00\x00O\x00\x00\x00M \x00\x00\x00>\x00\x00\x00{"メッセージ": "開始","クライアント": "134.106.74.21", "タイプ": 1009}', '', '')\x00 \x00\x001\x00\x00\x003\x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x000\x00\x00\x006 \x00\x00\x00. \x00\x00\x007\x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x002\x00\x00 \x005\x00\x00\x00"\x00\x00\x00 ,\x00\x00\x00 \x00\x00\x00"\x00\x00\x00t\x00\x00\x00y\x00 \x00\x00p\x00\x00\x00e\x00\x00\x00"\x00\x00\ x00:\x00\x00\x00 \x00\x00\x002\x00\x00\x000 \x00\x00\x000\x00\x00\x005\x00\x00\x00}\x00\x00\x00<\x00\x00 \x00E\x00\x00\x00O\x00\x00\x00M \x00\x00\x00>\x00\x00\x00{"メッセージ": "開始", "クライアント": "134.106.74.21", "タイプ": 1009}', '', '')\x00 \x00\x001\x00\x00\x003\x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x000\x00\x00\x006 \x00\x00\x00. \x00\x00\x007\x00\x00\x004\x00\x00\x00.\x00\x00\x001\x00\x00\x002\x00\x00 \x005\x00\x00\x00"\x00\x00\x00 ,\x00\x00\x00 \x00\x00\x00"\x00\x00\x00t\x00\x00\x00y\x00 \x00\x00p\x00\x00\x00e\x00\x00\x00"\x00\x00\ x00:\x00\x00\x00 \x00\x00\x002\x00\x00\x000 \x00\x00\x000\x00\x00\x005\x00\x00\x00}\x00\x00\x00<\x00\x00 \x00E\x00\x00\x00O\x00\x00\x00M \x00\x00\x00>\x00\x00\x00{"メッセージ": "開始", "クライアント": "134.106.74.21", "タイプ": 1009}', '', '')\x00\x00\x00 \x00\x00\x00"\x00\x00\x00t\x00\x00\x00y\x00 \x00\x00p\x00\x00\x00e\x00\x00\x00"\x00\x00\x00 :\x00\x00\x00 \x00\x00\x002\x00\x00\x000 \x00\x00\x000\x00\x00\x005\x00\x00\x00}\x00\x00\x00<\x00\x00\ x00E\x00\x00\x00O\x00\x00\x00M \x00\x00\x00>\x00\x00\x00{"メッセージ": "開始"、"クライアント": "134.106.74.21"、"タイプ": 1009 }'、''、'')\x00\x00\x00 \x00\x00\x00"\x00\x00\x00t\x00\x00\x00y\x00 \x00\x00p\x00\x00\x00e\x00\x00\x00"\x00\x00\x00 :\x00\x00\x00 \x00\x00\x002\x00\x00\x000 \x00\x00\x000\x00\x00\x005\x00\x00\x00}\x00\x00\x00<\x00\x00\ x00E\x00\x00\x00O\x00\x00\x00M \x00\x00\x00>\x00\x00\x00{"メッセージ": "開始"、"クライアント": "134.106.74.21"、"タイプ": 1009 }'、''、'')

更新しました

2 つの文字列を追加しようとしたときに問題が発生しました。

Hoare パーティショニングを使用した QuickSort を C コードに変換するのに苦労しており、その理由がわかりません。私が使用しているコードを以下に示します。

また、なぜ機能するのかよくわかりませんHoarePartition。誰かがそれが機能する理由を説明できますか、または少なくとも機能する記事に私をリンクできますか?

パーティショニング アルゴリズムの段階的なワークスルーを見てきましたが、直感的にはわかりません。私のコードでは、うまくいかないようです。たとえば、配列が与えられた場合

ピボット13を使用しますが、最終的に配列になります

そしてjどちらがを返しa[j] = 11ます。その時点からそれ以降の配列はすべてピボットよりも大きい値を持つべきだと思っていましたが、11 < 13 であるため、ここではそうではありません。

Hoare パーティショニングの疑似コード (CLRS、第 2 版から) を以下に示します。

ありがとう！

編集：

この問題に対する正しい C コードは次のようになります。

述語のリストに基づいてマップをマルチパーティション化しようとしています。

私はそれを行うために次の関数を書きました：

scala コンパイラ (私は 2.9.1 を実行しています) は、指定された場所で「型の不一致; 見つかった (A,B) => ブール値、必須: (A,B) => ブール値」で失敗します。

誰もそのようなものを見たことがありますか？それを修正する方法はありますか？

ありがとう、

LP

配列に存在するピボット要素に依存しないインプレース パーティショニングアルゴリズム (Quicksort 実装で使用される種類の)はありますか?

つまり、配列要素は次の順序で配置する必要があります。

• ピボットよりも小さい要素 (存在する場合)
• ピボットに等しい要素 (存在する場合)
• ピボットより大きい要素 (存在する場合)

ピボット要素が配列に存在する場合は (並べ替え後に) インデックスを返す必要があり、そうでない場合は特別な値を返す必要があります。これは、順序を維持するために要素を挿入できるインデックスの1 の補数である可能性があります (Java の標準のバイナリ検索関数の戻り値のように)。

私が見た実装では、ピボット要素のインデックスをパラメーターとして指定する必要があります (または常に配列の先頭にある必要があります)。残念ながら、ピボットが配列内に存在するかどうか (または配列のどこにあるか) は事前にわかりません。配列にあります。)

編集（メリットンのコメントへの返信）：次の条件のいずれかが当てはまると想定することもできます。

• 配列の長さが < 2、または
• 少なくとも 1 つの要素が <= ピボットで、少なくとも 1 つの要素が >= ピボットです。

配列内に値が重複している可能性があります (ピボット値の重複を含む)。

数値を受け取り、合計がその数値 (パーティション) になる数値のリストの をn返す再帰関数を定義しました。list

関数がnumberのパーティション数を返すようにする方法を考えていましたn。

たとえば、P(6)を返し10ます。