問題タブ [data-partitioning]

セット{1,2,3,4}から、正確に2つの部分を持つ異なるパーティションをいくつ作成できますか？このリストには、2つの部分に分割する必要がある4つの要素があります。私はこれらを書き留めて、合計7つの異なる可能性を得ました：

1. {{1}、{2,3,4}}
2. {{2}、{1,3,4}}
3. {{3}、{1,2,4}}
4. {{4}、{1,2,3}}
5. {{1,2}、{3,4}}
6. {{1,3}、{2,4}}
7. {{1,4}、{2,3}}

ここで、セット{1,2,3、...、100}について同じ質問に答える必要があります。このリストには、2つの部分に分割する必要がある100個の要素があります。パーティションの一部の最大サイズは50（100/2）で、最小サイズは1です（つまり、一方の部分には1つの番号があり、もう一方の部分には99があります）。考えられるすべての組み合わせの無関係なリストを書き出すことなく、2つの部分のパーティションにいくつの異なる可能性があるかをどのように判断できますか？答えを階乗（12など）に簡略化できますか？
k要素のセットで正確にn個のパーツを持つ異なるパーティションをいくつ作成できるかを見つけるために使用できる一般式はありますか？

私は現在、暇なときにアルゴリズムを学んでいますが、第3章のselect（）アルゴリズムを研究しているときに、次の質問があります。

Aからnまでの数の配列を使用している場合、select（）アルゴリズムを使用して中央値（n / 2番目に小さい数）を見つけることができることを理解しています。

1）しかし、これは私が理解するのに苦労しているビットです。A = [3、7、5、1、4、2、6、2]。それが配列だとします。Partition（）の各呼び出し後の配列の内容、およびSelect（）の各再帰呼び出しのパラメーターは何ですか。

誰かがこれをどのように解決しているか説明できますか？

以下は、2つのアルゴリズムの擬似コードです。

2番目のコードは

私が使用している本は、AnneKaldewaijによるTheDerivationofAlgorithmsと呼ばれています。

配列を通過させて、2 つの新しい配列を作成したいと思います。1 つは特定の条件を満たす要素を含み、もう 1 つは要素を満たさない配列です。

これは 1 回のパスで可能ですか、それとも必ず 2 回パスする必要がありますか? これが別のプログラミング言語または別のデータ構造でどのように機能するかはわかりますが、Java ではこれは不可能のようです。

クイックソートのインプレース パーティション サブルーチンを実装しようとしていました。一意の要素の配列で動作しますが、配列に重複要素が含まれていると失敗します

コードは次のようになります

入力が一意の要素の場合、コードは正しい結果を返します

以下の配列を試したところ、間違った結果が得られました

これは私の実装に問題があるためですか?誰かが少し助けてくれますか?

説明：nのパーティションがある場合、パーティション内の最小の項目から1を引くことにより、標準的な方法でn-1のパーティションに減らすことができます。例：1 + 2 + 3 => 2 + 3、2 + 4 => 1+4。このアルゴリズムはプロセスを逆にします。n-1のパーティションpごとに、このプロセスによってpに削減されるnのパーティションを見つけます。したがって、nの各パーティションは、それが減少するn-1のパーティションが考慮されるステップで、1回だけ出力されます。

これは、Pythonで数値の可能なすべてのパーティションを取得するためのコードです。私はPythonが苦手です。誰かがそれを擬似コード（または詳細な説明）またはPHPに変換していただければ幸いです。上記の説明は、「パーティション内の最小のアイテムから1つを差し引く」ことについての私の心に疑問を投げかけます。2番目に小さい要素または他の要素から1を引くこともできます。では、なぜ最小なのか？誰かが私に全体の考えを説明することができれば、それは本当にありがたいです。ありがとう。

Jon Bentley が彼の「美しいクイックソート コード」を紹介しているhttp://code.google.com/edu/algorithms/index.htmlのビデオを見るまでは、クイックソートの仕組みをよく理解していると思っていました。 :

私を混乱させるアルゴの別の部分は、FOR ループの後の最後のスワップです。なぜそれが必要なのですか？配列がすでに整っていると仮定しましょう。そうであれば、x[i] > x[l] であるためスワップは発生しません。最後に、l を m に置き換えます。それは注文を台無しにします。

何か不足していますか？

ありがとう。

配列を 2 つのリストに分割する並列アルゴリズムを C# で作成しました。1 つは特定の述語を満たす要素を含み、もう 1 つは述語を満たさない要素を含みます。これは順序保存アルゴリズムです。

以下のように書いていますが、ハードウェアの同時実行性から利益を得る機会を最大化する方法を知りたいです。

整数のパーティションの合計があり、すべての値が等しくないパーティションのみが必要です。例-3のパーティションは、{1,1,1,1}、{2,2}、{3,1}、{1,1,2}、および{4}です。したがって、必要な等しくないパーティションは、等しい要素が含まれていないため、{3,1}と{4}です。すべてのパーティションを見つけるために使用したコードを以下に示します。パーティションをフィルタリングして目的の結果を得ることができますが、すべてのパーティションを検索せずに、等しい用語が含まれていないすべてのパーティションを効率的に検索する方法が必要です。私はネットとスタックオーバーフローを検索しましたが、私が直面している問題を正確に述べているものは何もありません。すべてのアイデアは高く評価されています。ありがとう。

指定された整数のすべてのパーティションを生成する必要があります。
私は、ジェローム・ケレハーによるこのアルゴリズムを見つけました。これは、最も効率的なアルゴリズムであると言われています。

参照： http： //homepages.ed.ac.uk/jkellehe/partitions.php

ちなみに、あまり効率的ではありません。このような入力の場合40、出力を提供する前に、システム全体が数秒間フリーズします。

再帰的なアルゴリズムだとしたら、キャッシュ機能などで装飾して効率を上げようと思いますが、そういうわけではどうしたらいいのかわかりません。

このアルゴリズムを高速化する方法についていくつか提案がありますか？または、別のアプローチ、または別のアプローチを最初から作成するための別のアプローチを提案できますか？

リスト内の数値のパーティションを表す必要があります。このプロシージャは、パーティションの最大数と初期パーティションの最大値を決定する引数も取ります。

ここで、初期合計は5、最大パーティション数は2、最大初期パーティションは4です。

概念的には、パーティション化された数値を、パーティションを構築するヘルパー関数にフィードする必要があると思います。しかし、どうすればそれを実装できますか？

解決しました