3

この質問は、3 分割の組み合わせ状況の解または発見的近似を求めるで説明されているコンテキストに関連しています。タスクは、それぞれが評価された価値を持つ約 48 個の継承されたジュエリーを 3 人の継承者に分配し、各継承者に等しいまたはほぼ等しい価値を与えることです。その質問は、私の法的目的のために十分に答えられています.

この新しい問題は、列挙によってこれを解決するという私の追求から生じます。法的にはまったく不要です。今は単なる知的な挑戦です。

今の問題：

各項目に一意のインデックスを割り当てます。おそらく 1 ～ 48 の整数だけです。これらの 48 を 3 つの継承者のそれぞれに割り当て、重複を排除します。

この例のケースを簡単にするために、項目が 9 つしかなく、各継承者が正確に 3 つの項目を受け取ることをアサートします。(これは、3 つのビンをほぼ等しい値にするという以前の目標とは異なることに注意してください。)

アイテムからビンへの順序で重複を排除する方法は?

例:
ビン 1 にアイテム {1,2,3}
を含める ビン 2 にアイテム {4,5,6}
を含める ビン 3 にアイテム {7,8,9} を含める

このトリプレットのトリプレットの最終値の 6 つの重複があります:
{1,2,3}{4,5,6}{7,8,9}
{4,5,6}{1,2, 3}{7,8,9}
{4,5,6}{7,8,9}{1,2,3}
{7,8,9}{1,2,3}{4,5,6 }
{7,8,9}{4,5,6}{1,2,3}
など

繰り返しますが、アイテムからビンへの順序で重複を排除するにはどうすればよいですか? トリプレットの順列のセット全体を列挙することなく。いいえ、それは正しくありません。トリプレットのすべての順列を一時的に削除する必要があるかもしれません。アプリオリに行われたことに基づいて、重複したトリプレットの組み合わせをすばやく排除するにはどうすればよいですか?

3 つの項目の任意の組み合わせを指定すると、一意の値を返す関数を発明するようなものを想像できます。素数を使った何か？ただし、素数の多くのペアを合計すると別の素数になります。

元の質問を mathoverflow にクロスポストしました。stackoverflow と mathoverflow の関係が理解できておらず申し訳ありません。

4

2 に答える 2

3

制限されたパーティションの総数は

ここに画像の説明を入力、これは 280 に相当します。

これは、次のように並べ替えることができます。

ここに画像の説明を入力

これを取得するには、9 つ​​のリスト メンバーのうち 3 つを取得して得られる (順序付けられた) 組み合わせの最初の 3 分の 1 と、残りの 6 つのうち 3 つを最初の 3 つの選択肢ごとに取得するときに得られる組み合わせの前半を取得します。 . もちろん、最後の 3 つを自由に選択することはできません。

Mathematica では、これを次のように生成できます。

list = Range[9];
l1 = Subsets[list, {3}, Binomial[9, 3]/3];
l2 = Subsets[Complement[list, #], {3}, Binomial[6, 3]/2] & /@ l1;
Flatten[
  Outer[
    Function[{ll1, ll2}, {ll1, ll2, Complement[list, ll1, ll2]}], 
    {#1}, #2, 1, 1
  ] & @@@ ({l1, l2}\[Transpose]), 
2]

ここに画像の説明を入力

于 2011-12-28T23:09:02.687 に答える
2

これは良い質問です。これは基本的に、制限されたセット パーティションの問題です。

これにアプローチする方法の 1 つを次に示します。それが最適かどうかは定かではありませんが、ブルート フォース (すべての順列を生成してから重複を削除する) よりもはるかに効率的です。

私は中括弧を使ってリストを表現します。

次のテンプレートから始めます。これは、3 つのビンでゼロのアイテムを表します。

{ {{}, {}, {}} }

最も外側 (つまり、ここだけ) 内の各リストについて{{}, {}, {}}:

  1. 1いっぱいになった (3 つの要素を含む) リストをスキップして、各サブリストに追加し、複数ある場合は最初の空のリストにのみ追加します{}。

  2. 交換が行われるたびにリスト全体のコピーを保持し、ステップの最後にこれらを結合します。

2このプロセスは、3、 などに対して、すべてのアイテムがビンに入るまで、またはすべてのビンがいっぱいになるまで繰り返されます。手順の例:

{ {{}, {}, {}} }

{ {{1}, {}, {}} }

{ {{1, 2}, {}, {}}, {{1}, {2}, {}} }

{ {{1, 2, 3}, {}, {}}, {{1, 2}, {3}, {}}, {{1, 3}, {2}, {}}, {{1}, {2, 3}, {}}, {{1}, {2}, {3}} }

{ {{1, 2, 3}, {4}, {}}, {{1, 2, 4}, {3}, {}}, {{1, 2}, {3, 4}, {}}, {{1, 2}, {3}, {4}}, {{1, 3, 4}, {2}, {}}, {{1, 3}, {2, 4}, {}}, {{1, 3}, {2}, {4}}, {{1, 4}, {2, 3}, {}}, {{1}, {2, 3, 4}, {}}, {{1}, {2, 3}, {4}}, {{1, 4}, {2}, {3}}, {{1}, {2, 4}, {3}}, {{1}, {2}, {3, 4}} }
于 2011-12-22T08:22:30.347 に答える