交差する要素が 2 つ以上ない特別なタイプの組み合わせを作成したいと考えています。例を挙げて説明しましょう：
A、B、C、D、E、F、G、H、および I を含む 9 つの文字セットがあるとします。
繰り返しのない標準的な 3 文字の組み合わせを作成すると、9C3 セットになります。これらには、ABC、ABD、BCD などのセットが含まれます。一般的な文字が 1 つだけのセットを作成したいと考えています。したがって、この例では、次のセットを取得します。
ABC、ADG、AEI、AFH、BEH、BFG、BDI、CFI、CDH、CEG、DEF、および GHI - 2 つのセットを使用する場合、繰り返し文字は 1 つしかないことに注意してください。
そのようなセットを生成する良い方法は何でしょうか? サブセットサイズ4で、1000文字のセットに対して実行できるように、スケーラブルなソリューションである必要があります。
どんな助けでも大歓迎です。
ありがとう
n 個の手紙 (または学生など) があり、毎週それらをサイズ k のサブセットに分割したいとします (n/k毎週のサブセットの合計)。このメソッドは、ほぼn/k毎週サブセットを生成します。正確にn/kサブセットを生成するように拡張する方法を以下に示します。
最初に、最大の素数 <= n/k である p を選択します。
すべての順序付けられたペア (a,b) を考えてみましょう。
0 <= a < k
0 <= b < p
各ペアを文字の 1 つにマッピングできます。したがって、p*k <= nこの方法で文字をマッピングできます(繰り返しますが、正確に n 文字をマッピングする方法を以下に示します)。
(0,0) => 'A'
(0,1) => 'B'
...
(0,p-1) => 'F'
(1,0) => 'G'
(1,1) => 'H'
...
(k-1,p-1) => 's'
今、与えられた
0 <= w < p
0 <= i < p
順序付けられたペアのセット S w (i) を作成できます。S w (i)の各ペアは(上記のマッピングに従って) 1 つの文字を表し、集合 S w (i) 自体は 1 つの「文字のグループ」別名を表します。サイズ k の 1 つのサブセット。
S w (i) の式は次のとおりです。
S w (i) = {(0,i mod p), (1,(w+i) mod p), (2,(2w+i) mod p),..., ((k-1), ((k-1)*w+i) mod p)}
= { (x,y) | 0 <= x < k および y = w*x + i (mod p)}
w と i をすべての可能な値で変化させると、p 2個の合計セットが得られます。これらのセットのいずれか2 つを取得すると、交差する要素は最大で 1 つになります。
2 つの集合 S w1 (i 1 ) と S w2 (i 2 ) があるとします。S w1 (i 1 ) と S w2 (i 2 ) に複数の共通要素がある場合、少なくとも 2 つの要素が存在しx、
w 1 *x + i 1 = w 2 *x + i 2 (mod p) (w 1 -w 2 )*x + (i 1 -i 2 ) = 0 (mod p)
ただし、剰余演算を行ったことのある人なら、p が素数の場合、x が一意の解を持つか、または (w 1 = w 2および i 1 = i 2 );であることを知っています。したがって、複数の x が存在することはできず、S w1 (i 1 ) と S w2 (i 2 ) は最大で 1 つの交差要素を持つことができます。
以来p < n/k、チェビシェフの定理(x > 3 の場合、x と 2x の間に素数があると述べています)
n/2k < p <= n/k
したがって、このメソッドは少なくとも (n/2k) 2文字のサブセットを生成しますが、実際には p は n/k に近いため、数は (n/k) 2に近くなります。このようなサブセットの最大可能数の単純な上限はn(n-1)/(k(k-1))(以下の BlueRaja のコメントを参照) であるため、これは、アルゴリズムが漸近的に最適であり、最適な量のセットに近い値を生成することを意味します (最悪の場合でも、生成されるセット数より少なくなることはありません)。最適な量の約 1/4; 以下のコメントをもう一度参照してください)
ここで、レターを毎週パーティションにグループ化する必要があります。毎週、すべてのレターが 1 つのグループに含まれます。
これを行うwには、特定の値 (週を表す) に固定し、i0 から p-1 まで変化させます。
作成したグループについて考えてみましょう。
S w (i) = { (x,y) | 0 <= x < k および y = w*x + i (mod p)}
wが固定されており、0 から p-1 まで変化するとしiます。次に、p セットを取得します。
S w (0)、S w (1)、...、S w (p-1)
ここで、S w (i 1 ) と S w (i 2 ) (i 1 =/= i 2 ) が交差するとします。それから
w*x + i 1 = w*x + i 2 (mod p)
ある x に対して、したがって i 1 = i 2 . したがって、S w (i 1 ) と S w (i 2 ) は交差しません。
交差するセットは 2 つとなく、正確に p 個 (それぞれに k 個の要素がある) があるため、セットは k*p 文字の分割を形成します。
この方法の最大の欠点は、n 文字ではなく p*k 文字のセットを生成することです。最後の文字を除外できない場合 (文字が学生の場合のように)、毎週正確に n/k サブセットを生成する方法が 2 つあります。
素数 p 1、 p 2、 p 3、... の集合を見つけてください。合計すると正確に n/k になります。次に、p i k 文字の各グループを独立したアルファベットとして扱うことができるため、p k 文字のサブセットを見つけるのではなく、 p 1 *k 文字のサブセットの 1 つのグループと、p 2 *k 文字のサブセットの別のグループを見つけることができます。 、別のグループ...これには、あるグループの文字が別のグループの文字と決してペアにならず、生成されるサブセットの総数が減るという
欠点があります。幸いなことに、n が偶数の場合、ゴールドバッハの予想† により、必要なグループは最大で 2 つだけです (n が奇数の場合、必要なグループは最大で3 つだけです)。)
この方法は、サイズ k のサブセットを保証しますが、それほど多くのサブセットを生成しません。
†証明されていませんが、この問題で遭遇する可能性が高いすべての途方もなく大きな数に当てはまることが知られています。
もう 1 つのオプションは、最小の素数 p >= n/k を使用することです。これにより、 p*k >= n 文字が得られます。サブセットが生成された後、余分な文字を単に破棄します。したがって、最終的にこれにより、サイズ < k のサブセットが得られます。k が n を均等に分割すると仮定すると (つまり、n/k は整数)、より小さいサブセットを取得し、それらを手動で混合してサイズ k のサブセットを作成できますが、この方法では過去/将来のサブセットと重複するリスクがあります。
このメソッドは、少なくとも元のメソッドと同じ数のサブセットを生成しますが、一部のサイズは k 未満になる場合があります
n = 15、k = 3 とします。つまり、15 人の生徒がいて、3 人でグループを作っています。
まず、最大の素数 p <= n/k を選択します。n/kは素数なので(幸運なことに!)、p = 5 です。
15 人の生徒を上記の順序付けられたペア (a、b) にマッピングすると、次のようになります (各文字は生徒です)。
(0,0) = A
(0,1) = B
(0,2) = C
(0,3) = D
(0,4) = E
(1,0) = F
(1,1) = G
(1,2) = H
(1,3) = I
(1,4) = J
(2,0) = K
(2,1) = L
(2,2) = M
(2,3) = N
(2,4) = O
このメソッドは、3 つのグループを 25 個生成します。したがって、毎週 n/k = 5 グループをスケジュールする必要があるため、5 週間のアクティビティをスケジュールできます (1 週間に 5 グループ * 5 週間 = 25 グループ)。
週 0 では、パーティションを次のように生成します。
S 0 (i)、i = 0 ～ 4 の場合。
S 0 (0) = { (0,0), (1,0), (2,0) } = AFK
S 0 (1) = { (0,1), (1,1), (2,1) } = BGL
S 0 (2) = { (0,2), (1,2), (2,2) } = CHM
S 0 (3) = { (0,3), (1,3), (2,3) } = DIN
S 0 (4) = { (0,4), (1,4), (2,4) } = EJO
4週目は
S 4 (i) i = 0 ～ 4 の場合。
S 4 (0) = { (0,0), (1, (4*1 + 0) mod 5), (2, (2*4 + 0) mod 5) }
= { (0,0), (1,4), (2,3) }
= AJN
S 4 (1) = { (0,1), (1, (4*1 + 1) mod 5), (2, (4*2 + 1) mod 5) }
= { (0,1), (1,0), (2,4) }
= BFO
S 4 (2) = { (0,2), (1, (4*1 + 2) mod 5), (2, (4*2 + 2) mod 5) }
= { (0,2), (1,1), (2,0) }
=CGK
S 4 (3) = { (0,3), (1, (4*1 + 3) mod 5), (2, (4*2 + 3) mod 5) }
= { (0,3), (1,2), (2,1) }
= DHL
S 4 (4) = { (0,4), (1, (4*1 + 4) mod 5), (2, (4*2 + 4) mod 5) }
= { (0,4), (1,3), (2,2) }
= EIM
全5週間のスケジュールは次のとおりです。
週: 0
S 0 (0) ={(0,0) (1,0) (2,0) } = AFK
S 0 (1) ={(0,1) (1,1) (2,1) } = BGL
S 0 (2) ={(0,2) (1,2) (2,2) } = CHM
S 0 (3) ={(0,3) (1,3) (2,3) } = DIN
S 0 (4) ={(0,4) (1,4) (2,4) } = EJO
1週目
S 1 (0) ={(0,0) (1,1) (2,2) } = AGM
S 1 (1) ={(0,1) (1,2) (2,3) } = BHN
S 1 (2) ={(0,2) (1,3) (2,4) } = CIO
S 1 (3) ={(0,3) (1,4) (2,0) } = DJK
S 1 (4) ={(0,4) (1,0) (2,1) } = EFL
週: 2
S 2 (0) ={(0,0) (1,2) (2,4) } = AHO
S 2 (1) ={(0,1) (1,3) (2,0) } = BIK
S 2 (2) ={(0,2) (1,4) (2,1) } = CJL
S 2 (3) ={(0,3) (1,0) (2,2) } = DFM
S 2 (4) ={(0,4) (1,1) (2,3) } = EGN
週: 3
S 3 (0) ={(0,0) (1,3) (2,1) } = AIL
S 3 (1) ={(0,1) (1,4) (2,2) } = BJM
S 3 (2) ={(0,2) (1,0) (2,3) } = CFN
S 3 (3) ={(0,3) (1,1) (2,4) } = DGO
S 3 (4) ={(0,4) (1,2) (2,0) } = EHK
週: 4
S 4 (0) ={(0,0) (1,4) (2,3) } = AJN
S 4 (1) ={(0,1) (1,0) (2,4) } = BFO
S 4 (2) ={(0,2) (1,1) (2,0) } = CGK
S 4 (3) ={(0,3) (1,2) (2,1) } = DHL
S 4 (4) ={(0,4) (1,3) (2,2) } = EIM
あなたの場合、各グループの n = 1000 人の学生と k = 4 です。したがって、p を最大の素数 <= (n/k = 1000/4 = 250) として選択するため、p = 241 です。上記の「毎週 n/k サブセットを生成する」の下の変更を考慮しなくても、このメソッドはスケジュールを生成します。 241週間続く961人の学生のために。
(可能なサブセットの最大数の上限は 1000*999/(4*3) = 83250 ですが、実際の数はそれより少ない可能性があります。それでも、このメソッドは 58081 のサブセット、または約 70% を生成します。理論上の最大値!)
上記の最初の方法を使用して正確に 1000 人の学生のスケジュールを生成する場合、p 1 = 113、p 2 = 137 となります (p 1 + p 2 = n/k となります)。したがって、(113)^2 + (137)^2 = 31,538 個の生徒のサブセットを生成でき、113 週間続くのに十分です。
上記の 2 番目の方法を使用して、正確に 1000 人の学生のスケジュールを生成する場合、p = 251 を取ります。これにより、251 週間で 1004 人の学生のスケジュールが得られます。毎週スケジュールから 4 人の幻の生徒を削除します。通常、これにより、毎週 3 人が 4 つのグループになります(可能性は低いですが、たとえば、2 人が 1 つのグループと 3 人が 2 つのグループになることもあります)。 学生が 4 人未満のグループには、常に学生の合計数が 4 の倍数になるため、それらの学生を 4 人のグループに手動で配置することができますが、これらの学生のうちの 2 人が後で別のグループで再び一緒になる可能性があります。
このアルゴリズムの欠点の 1 つは、実際には柔軟性がないことです。学生が中退すると、幻の学生と永遠に行き詰まることになります。また、年度の途中で新しい生徒をスケジュールに追加する方法はありません (最初に幻の生徒を作成して許可しない限り)。
この問題は、組み合わせ論における制限付き集合システムのカテゴリに分類されます。詳細については、この論文、特に第 1 章と第 2 章を参照してください。Postscript ファイルなので、表示するには gsview などが必要です。
I had to add another answer as the other one was too long already.
If you have the following constraints:
1) You need groups of 4 every week.
2) Each group in a certain week is disjoint and each student is in exactly one group.
3) If two students are in the same group, they need cannot be in the same group in future.
If you construct a graph G as follows:
1) Each student is a node.
2) 2 人の生徒がグループで一緒になったことがない場合、エッジで結合されます。
学生が勝手に脱退・入団することは、大変な問題です！最初は完全なグラフから始めても、数週間後にはグラフがまったく予測不能になる可能性があります。
あなたの問題: K_4 のコピーの和集合、つまり K_4 への分割となるように、G のスパニング サブグラフを見つける必要があります。
残念ながら、この問題は NP-Hard のようです: 4 セットによる正確なカバー (NP 完全) は、問題に縮小できます (3 セットによる正確なカバーを三角形に分割するために縮小できるように)。
おそらく、これはいくつかの近似アルゴリズムを提供するのに役立ちます: http://www.siam.org/proceedings/soda/2010/SODA10_122_chany.pdf
(問題は Hypergraph マッチングに還元できるため、そのアルゴリズムを問題に使用できます)。
正確な表紙: http://en.wikipedia.org/wiki/Exact_cover
三角形に分割: https://noppa.tkk.fi/noppa/kurssi/t-79.5103/viikkoharjoitukset/T-79_5103_solutions_5.pdf
4 セットによる正確なカバー = サイズ 4m のセット S と、S の 4 要素サブセットの集合 C が与えられた場合、S の各要素が C' に正確に 1 回現れるように、C のサブセット C' は存在しますか?
残念ながら、いくつかの制約を変更する必要があるようです。
これは、あなたが述べた要件を満たすアプローチです。それがあなたの望むようになるかどうかはわかりません。
これを実際のコードに変換するのはあなたに任せますが、それほど難しくはなく、うまくスケーリングできるはずだと思います。他のサイズのサブセットでも機能するはずであることに注意してください。困難になる可能性がありますが、任意の n に対して不規則な n-gons を使用して平面をタイル張りすることができます。
私が考えた他のアプローチは次のとおりです。
これにはもう少し簿記が必要であり、対処しなければならないまれなケースがいくつかありますが、コードを作成するのはそれほど難しくありません。
編集:私の最初のアプローチを、より明らかにグラフ上のアルゴリズムである形式に変換するのは簡単です。各サブセットをノードとしてモデル化し、アルファベットの各文字をエッジとしてモデル化します。各ノードが次数 n (サブセット内の要素の数) を持ち、各文字 (エッジ) が 1 回使用されるグラフを作成します。
アルゴリズムの概要を次に示します。
これらは、6 個の n(n-1) の配列に格納できます。
次のルールを使用して、連続するペアの結合を試みます。共通の文字がある場合にのみ、2 つのペアを組み合わせることができます。b. 共通のキャラクターを残したペアも存在する場合、組み合わせが可能です。たとえば、AB と AC を組み合わせたい場合は、BC も利用できるかどうかを確認する必要があります。c. 上記のルールが満たされると、2 つのペアを組み合わせてトリプルにし (たとえば、AB と AC を結合して ABC を形成)、AB、AC、BC などの 3 つのペアすべてを使用不可としてマークします。
配列内で使用可能なペアを探し、それらをマージしてトリプルを形成し、使用可能なペアがなくなるか、トリプルを形成できなくなるまでペアを使用不可としてマークすることを続けます。
例: 1. AB + AC --> ABC を組み合わせます。AB、AC、および BC を使用不可とマークします。2. AD + AE を組み合わせる --> AED; AD、AE、DE を使用不可とマークします。3. AF + AG --> AFG を組み合わせます。AF、AG、FG を使用不可にします。..
@khuss
同じ方法を一般化できます。ただし、これは線形アルゴリズムではなく、指数関数的である可能性があります。
例: サブセット サイズが 4 の場合、4 つの固有の文字を持つ 2 つ以上のペアを選択します。
たとえば、「AB and CD」または「AB, AC & AD」は、次の条件が満たされている場合のみ:
これ以上 4 タプルが形成できなくなるか、使用可能なペアがなくなるまで、以前と同様に続行します。