|
Since 2015.2.11 |
下の計算式を見て下さい。
なんと、２４人、６組の場合は、４．５兆通りもの組み合わせ数があります。
この中から、過去の一緒に回っていない人の組み合わせを抽出するには、少し工夫が必要です。
●８人：（4人、4人）の２組の場合
8×7×6×5×4×3×2
──────────── ＝ 35 通り
(4×3×2)×(4×3×2)×2
＜補足＞
(4×3×2)：１組の中の冗長数を省きます。
すなわち、
(01)a,b,c,d (02)a,b,d,c (03)a,c,b,d (04)a,c,d,b (05)a,d,b,c (06)a,d,c,b
(07)b,a,c,d (08)b,a,d,c (09)b,c,a,d (10)b,c,d,a (11)b,d,a,b (12)b,d,b,a
(13)c,a,b,d (14)c,a,d,b (15)c,b,a,d (16)c,b,d,a (17)c,d,a,b (18)c,d,b,a
(19)d,a,b,c (20)d,a,c,b (21)d,b,a,c (22)d,b,c,a (23)d,c,a,b (24)d,c,b,a
は、同じ組み合わせになります。
最後の2は、4名、4名の２組の冗長数です。
●１２人：（4人、4人、4人）の３組の場合
12×11×10×9×8×7×6×5×4×3×2
───────────────────── ＝ 5,775 通り
(4×3×2)×(4×3×2)×(4×3×2)×(3×2)
＜補足＞
最後の(3×2)は、4名、4名、4名の３組の冗長数です。
●１６人：（4人、4人、4人、4人）の４組の場合
16×15×14×13×12×11×10×9×8×7×6×5×4×3×2
──────────────────────────── ＝ 2,627,625 通り (約 262万通り)
(4×3×2)×(4×3×2)×(4×3×2)×(4×3×2)×(4×3×2)
＜補足＞
最後の(4×3×2)は、4名、4名、4名、4名の４組の冗長数です。
●２０人：（4人、4人、4人、4人、4人）の５組の場合
20×19×18×1716×15×14×13×12×11×10×9×8×7×6×5×4×3×2
────────────────────────────────── ＝ 2,546,168,625 通り (約 25億通り)
(4×3×2)×(4×3×2)×(4×3×2)×(4×3×2)×(4×3×2)×(5×4×3×2)
＜補足＞
最後の(5×4×3×2)は、4名、4名、4名、4名、4名の５組の冗長数です。
●２４人：（4人、4人、4人、4人、4人、4人）の６組の場合
24×23×22×21×20×19×18×1716×15×14×13×12×11×10×9×8×7×6×5×4×3×2
─────────────────────────────────────────── ＝ 4,509,264,634,875 通り (約 4.5兆通り)
(4×3×2)×(4×3×2)×(4×3×2)×(4×3×2)×(4×3×2)×(4×3×2)×(6×5×4×3×2)
＜補足＞
最後の(6×5×4×3×2)は、4名、4名、4名、4名、4名、4名の６組の冗長数です。
解決のための工夫 次のように考える
●１２人：（4人、4人、4人）の３組の場合
11C3 × 35 = 165 × 35 = 5,775
＊最初の１人を固定して、残りの１１人から３名を選び、４人・４人の組み合わせの35通りを掛ける。
●１６人：（4人、4人、4人、4人）の４組の場合
15C3 × 11C3 × 35 = 455 × 165 × 35 = 2,627,625
＊最初の１人を固定して、残りの１５人から３名を選び、[１２人]で選んだ分を掛ける。
●２０人：（4人、4人、4人、4人、4人）の５組の場合
19C3 × 15C3 × 11C3 × 35 = 969 × 455 × 165 × 35 = 2,546,168,625 (約 25億通り)
＊最初の１人を固定して、残りの１９人から３名を選び、[１６人]で選んだ分を掛ける。
●２４人：（4人、4人、4人、4人、4人、4人）の６組の場合
23C3 × 19C3 × 15C3 × 11C3 × 35 = 1,771 ×969 × 455 × 165 × 35 = 4,509,264,634,875 (約 4.5兆通り)
＊最初の１人を固定して、残りの２３人から３名を選び、[２０人]で選んだ分を掛ける。
改善の履歴 2015.12.27
９〜１６名用を、2015.11.15 に完成させましたが、その時の処理速度は、下記の表の通りでした。
（これでも、改善を行いましたが）
| 分：秒 | １回目（履歴なし） | ２回目（履歴１） | ３回目（履歴２） | ４回目（履歴３） | ５回目（履歴４） | ６回目（履歴５） |
| 改善前 | １秒 | １２秒 | １分４７秒 | １分５２秒 | １分５７秒 | ２分００秒 |
| 改善後 | １秒 | １秒 | １２秒 | ６秒 | １秒 | １秒 |
次に２０名用に取りかかりました。
２０名用を上記のアルゴリズムで、処理を行った場合、なんと、処理に４８時間もかかりました。
１０万通りの組み合わせを抽出し、比較するのに約７秒かかりました。
（２５億通り÷１０万通り）× ７秒 ＝ ２５，０００ × ７秒 ＝ １７５，０００秒 ＝ 約４８時間
それでも、１０万通りを７秒で処理できるので、コンピュータはすごいと思います。
しかしながら、これではとても使い物にならないので、アルゴリズムの基本構想を追加しました。
＜追加アルゴリズム＞
過去の組み合わせで、対戦したパターンを最大限、省く処理を行う。
(1) 一番対戦相手の少ない人の抽出
(2) その一番少ない人と対戦している人を省く
(3) １組目（４名）を選出 かつ、この４名が対戦していないかチェック
(4) 仮の１組目ができれば、残りの人を抽出
以下、上記の(1)〜(4)までを繰り返す。
＜改善結果＞
２０人：（4人、4人、4人、4人、4人）の５組の場合 = 2,546,168,625 (約 25億通り)
２４人：（4人、4人、4人、4人、4人、4人）の６組の場合 = 4,509,264,634,875 (約 4.5兆通り)
と膨大な組み合わせパターンがありますが、
処理が遅い場合でも、８秒程度 で処理が行えるようになりました。 パターン８へ
１６名での組み合わせで、５回、一緒の人と回らない組み合わせができます。
ただし、うまく組み合わせないと、４回目から、組み合わせができないことがあります。
【１６名が５回、同じ組み合わせにならない組み合わせ】
a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p の１６名の場合
| １回目 | ２回目 | ３回目 | ４回目 | ５回目 |
|
a,c,d,e b,g,h,j f,k,l,m i,n,o,p |
a,b,f,i c,g,m,p d,h,k,n e,j,l,o |
a,g,k,o b,c,l,n d,f,j,p e,h,i,m |
a,h,l,p b,d,m,o c,i,j,k e,f,g,n |
a,j,m,n b,e,k,p c,f,h,o d,g,i,l |
【組合せ（対戦）一覧】
| a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | |
| a | ★ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| b | 1 | ★ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| c | 1 | 1 | ★ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| d | 1 | 1 | 1 | ★ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| e | 1 | 1 | 1 | 1 | ★ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| f | 1 | 1 | 1 | 1 | 1 | ★ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| g | 1 | 1 | 1 | 1 | 1 | 1 | ★ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| h | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ★ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| i | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ★ | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| j | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ★ | 1 | 1 | 1 | 1 | 1 | 1 |
| k | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ★ | 1 | 1 | 1 | 1 | 1 |
| l | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ★ | 1 | 1 | 1 | 1 |
| m | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ★ | 1 | 1 | 1 |
| n | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ★ | 1 | 1 |
| o | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ★ | 1 |
| p | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ★ |
⇒ 対戦一覧が、綺麗に”１”が並びます。
【１６名が４回目では、組み合わせができない例】
a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p の１６名の場合
| １回目 | ２回目 | ３回目 | ４回目 | ５回目 |
|
a ,b ,c ,d e ,f ,g ,h i ,j ,k ,l m ,n ,o ,p |
a ,e ,i ,m b ,n ,k ,f c ,g ,j ,o d ,h ,l ,p |
a ,f ,j ,p b ,i ,o ,h c ,e ,l ,n d ,g ,k ,m |
|
【組み合わせ（対戦）一覧】 ３回の対戦一覧。４回目は、組み合わせができない。
|
参考
【組み合わせ（対戦）一覧】 ３回の対戦一覧。４回目の組み合わせができる場合
|
⇒ 見た感じ、同じようですが、
２回目、３回目の組み合わせをうまく考えないと、
４回目は、過去３回で、誰かと一緒に回った人がでてきます。
組み合わせの妙 【画面を広く取っています】