2

サイズnの集合Sが与えられ、これはサイズn1、..、nkのクラス（s1、..、sk）に分割されます。当然、n = n1 + ...+nkであることが成り立ちます。

このパーティショニングの要素を組み合わせて、各組み合わせに各クラスの要素が1つだけ含まれるようにする方法の数を知りたいと思います。

s1からn1要素、s2からn2要素などを選択できるので、n1 + .. + nkを保持する任意のn1、.. nkのmax（n1 * .. * nk）の解を探しています。 =n。

これは線形最適化の問題だと感じていますが、学部生として学んだので長すぎます。誰かがこれを計算する方法を覚えていることを願っています。

4

2 に答える 2

3

各パーティションの1つの要素との組み合わせの数をお探しですか？

それは単にn1*n2 * ...*nkです。

編集：あなたはまた別の質問をしているようです：

Nが与えられた場合、それらの積が最大になるようにn1、n2、...、nkを割り当てるにはどうすればよいですか。変数が乗算されるため、これは実際には線形最適化の問題ではありません。

これは、いくつかの微積分によって解決できます。つまり、ラグランジュ乗数を使用して、制約付きで各変数の部分的な派生変数を取得することによって解決できます。

その結果、n1..nkは可能な限り同じサイズに近くなるはずです。

if n is a multiple of k, then n_1 = n_2 = ... = n_k = n/k

otherwise, n_1 = n_2 = ... = n_j = Ceiling[n/k]
      and  n_j+1 = ... = n_k = floor[n/k]

基本的には、要素をパーティションにできるだけ均等に分散するようにしています。彼らが均等に分かれるなら、素晴らしい。そうでない場合は、可能な限り均等に分割し、残っているものはすべて、最初のパーティションにそれぞれ追加の要素を割り当てます。（最初のパーティションである必要はありません。その選択はかなり恣意的です。）このように、任意の2つのパーティションが所有する要素の数の差は最大で1つになります。

ゴーリーの詳細：

これは、私たちが最大化したい製品機能です。

P = n1 * n2 * ... nK

ラグランジュ乗数を使用して新しい関数を定義します。

ラムダ=P+ l（N-n1-n2 ... -nk）

そして、kn_i変数のそれぞれで偏導関数を取ります。

dLambda / dn_i = P / n_i --l

そしてlで：

dLambda / dl = N-n1 -n2 ... -nk

すべての偏導関数を=0に設定すると、k + 1方程式のシステムが得られ、それらを解くと、n1 = n2 = ...=nkが得られます。

いくつかの便利なリンク：

ラグランジュ乗数

最適化

于 2009-02-27T22:40:50.460 に答える