は問題である。は関係の下でn個のオブジェクトの可能な順序付けの数を計算<ここで=
入力としてnは正の整数をとり、nはオブジェクトの可能な順序付け の数を計算するアルゴリズムを与えます関係<および=の下にあります。たとえば、n = 3の場合、13の可能な順序は次のとおりです。
a = b = c,
a = b < c,
a < b = c,
a < b < c,
a < c < b,
a = c < b,
b < a = c,
b < a < c,
b < c < a,
b = c < a,
c < a = b,
c < a < b,
c < b < a.
アルゴリズムはnで時間多項式で実行する必要があります。
この問題は発生しません。このダイナミックプログラミングの問題に対する解決策はありますか？
F（N、k）は、正確にk個の不等式関係（及び（N - 1 - k）の品質の関係）との可能な順序付けの数とします。
f（n、0）= 1、f（n、n-1）= n！任意のnに対して。
ここで、任意のkに対してf（n、k）を計算します。想像してみれば、あなたは1つの番号（any）を移動したので、（n-1）の番号があることを想像してください。
1）これらの（n-1）個の数字に（k-1）個の不等式があり、（k + 1）（f（n-1、k-1）新しい不等式が追加されるようにn番目の番号を追加します。
2）これらの（n-1）個の数字にはk個の不等式があり、さらに不等式なしでn番目の数字を追加するには（k + 1）（f（n-1、k） f（n、k）=（k + 1）（f（n-1、k-1）+ f（n-1、k））である。 f（n）+ f（n、1）+ ... + f（n、n-1）。
あなたはこのために再帰関数を持つことができます。
F(1) = 1;
F(2) = 3;
F(n) = F(n-1) * n + F(n-2) * n*(n-1)/2 + F(n-3) * n*(n-1)(n-2)/3!+.... + F(1) * n + 1;
例
F(2) = 1 * 2 +1 = 3;
F(3) = F(2) * 3 + F(1) * 3 + 1 = 9 + 3 + 1 = 13;
はなぜか？
は、あなたがあなたの順序でAnを挿入したい、Anが0,1,2にすることができ、今F(n-1)を知っていると思う...シーケンス内のn番目の場所、関係なく、シーケンスの数カウント：
[A0,...An-1] < An this can be as [A0,...An] < An-1,...
のでn * f(n-1)配列が<
how many sequences end with one `=` sign? f(n-2) * n * (n-1)/ 2 why? ... (think yourself it's easy)
how many sequences end with "K" "=" sing? f(n-k+1) * n * ...*(n-k+1)/ k!
で終了あり、完全な1つの配列が存在する=
これは多項式で簡単に計算できます。
ちょうど<があれば、サイズNのセットをN個注文することができます。違う方法。
戻って=を追加すると、セットのパーティションを等価クラスの数に変えることができます。また、それらを並べ替える方法の数を掛けることもできます。
たとえば、サイズのセットを3つ（例のように）しましょう。 1つ、2つまたは3つの等価クラスを持つことができます。 1つの等価クラス、2つの等価クラスを持つ3つの方法、3つの等価クラスを持つ1つの方法しかありません（これらの計算方法については後で参照してください）。これは1 * 1を与える！ + 3 * 2！ + 1 * 3！ = 13の合計発注。
これは、元の問題を単純なものに分割します。つまり、セットをk個の部分に分割する方法を数えます。
sum(k! * S(N, k) for k in 1, 2, ..., N).
パーティションをカウントするためにこれらの漸化式を使用することができます（http://en.wikipedia.org/wiki/Stirling_number_of_the_second_kindを参照してください）：あなたがこれを行うには、関数S（N、k）を記述する場合、あなたは計算することによって、元の問題への答えを得ることができます
S(N, k) = S(N - 1, k - 1) + k * S(N - 1, k)
S(N, 1) = 1
S(N, N) = 1
ダイナミックプログラミングを使用してこの機能を計算することができます。