順列組合せについて

質問

１２名で年６回ゴルフコンペを行っております。
４名１組で計３組でラウンドしておりますが
この６回の内に他の11名すべての人と
なるべく重複しないように組を組むには
どういった組み合わせ方をすれば
良いでしょうか？
宜しくお願い致します。

回答No.5

stomachman · ベストアンサー

「みんなに一度は当たる」というだけの条件だったら、高々５回のラウンドでできちゃうんです。

　まず、条件を追加して、手作業で扱える程度の問題に帰着してしまいます。どんな条件かと言うと：
　12人のメンバーを1さんから12さん、と呼ぶことにします。（いや、●chとは関係ないです。）
で、二人ずつペアになって貰います。
ペア1は1さんと7さん、ペア2は2さんと8さん、ペアnはnさんとn+6さん(n=1～6)
こうして決めたペアはいつも一緒の組になる。これが追加した条件です。
　そうすると、
ラウンド1ではペア1～6はそれぞれA組,A組,B組,B組,C組,C組
ラウンド2ではペア1～6はそれぞれA組,B組,A組,C組,B組,C組
ラウンド3ではペア1～6はそれぞれA組,B組,C組,A組,C組,B組
ラウンド4ではペア1～6はそれぞれA組,B組,C組,B組,A組,C組
ラウンド5ではペア1～6はそれぞれA組,B組,B組,C組,C組,A組
という解がすぐ見つかりました。
　どのペアも他の5つのペアと一度は一緒にラウンドしてます。ですから、どの人も他の人全員と一度はラウンドしたことになる。だからこれで、「みんなに一度は当たる」という条件を満たしています。

　ただ、この組み合わせ方では、どの人もペアを組んだ相手とはいつも一緒である。これをもっと散らして平準化したいですね。

　そこで1～6さんは上記の組み合わせに従って戴くとして、7～12さんには以下のように組を代わって貰います。
ラウンド2と3ではA組と言われたらB組へ、B組と言われたらC組へ、C組と言われたらA組へ行く。
ラウンド4と5ではA組と言われたらC組へ、B組と言われたらA組へ、C組と言われたらB組へ行く。
　こうしますと、5回のラウンドのうちで、どの人も他の全員と当たり、しかも高々３回しか同じ人と当たりません。
　3回当たるのは
(1,8),(2,7),(3,10),(4,9),(5,12),(6,11)
　2回当たるのは
(1,9),(1,10),(2,9),(2,10),
(3,11),(3,12),(4,11),(4,12),
(5,7),(5,8),(6,7),(6,8)
で、他の「二人の組み合わせ」は1回ずつ当たります。

　ところで、6回のラウンドを有効に使えばもっと平準化できる（同じ人と1回しか当たらないということを減らすとともに、同じ人に3回当たるという組み合わせを少なくできる）に違いなく、コンピュータで力任せに探索すればナントカなるはず。そのうちやってみるかも知れません。

お礼

詳しい例をあげて頂きありがとうございます。
2回続けて同じ人とラウンドすることは
実際多々ありましたので組合せ的に避けられないことだと
思っていました。
今回このパターンに当てはめて組合せ表を
作ってみたところ3回当たる（2.7）の人だけ
連続3回一緒にラウンドすることになりますが
これはラウンド2を最後に回すことで
回避出来ますよね？
お忙しいところありがとうございます。

回答No.4

graphaffine

odenon909さん、今晩は。#1のものです。この週末に
家でプログラムを作って結果を出そうとしたら土日とも
休日出勤と相成ってしまいました。（泣）
さて、私もstomachmanさんの条件(1')(2)(3)を充たすものを探そうとしています。

(1') 任意の対は高々３回しか実現しない。
(3) 任意の対が少なくとも一回は実現される。
(2) ３人の組合せは高々一回しか実現しない。

で、プログラミングの方針として次の二つのものを立てました。
この方針に則ってプログラムを作ってくれる奇特な人はいないかな。
ただ、組み合わせ論に慣れた人でないと結構大変だろうけど。
勿論時間ができれば、私が作ります。（締め切られていない場合ですが)

方針１　強引な方法
ラウンドとは12人を4人からなる3つの集合に分割したもの。
（以降は、便宜上10番目、11番目、12番目の人を夫々A,B,Cで表わす)
従って、その全体（以下ROUNDとする）はC(11,3)C(7,3)=5775通り。
第１ラウンドは次のように決めて良い。
R1:[1234][5678][9ABC]
従って、２～６ラウンドをどう決めるかが問題。

１　12人中の3人の組合せは全部でC(12,3)=220通りだが、R1で12通りの
3人組みが既に実現されている。この12通りの集合をAとする。

２　12人中の4人の組合せは全部でC(12,4)=495通りだが、R1の４つと
集合Aを含む4人組みを全て取り除く。得られた集合をＸとする。

３　ROUNDからＸの要素に含まれない４人組みを含むラウンドを取り除く。
得られた集合をＹとする。

ここでかなりのギャップ。

４　Ｙの要素の５個の組で同じ３人組を含まないものを全て求める。

５　４で得たものの中で、条件(2)(3)を充たすものを取出す。

方針２（組合せ理論のある定理を使った方法）はまた明日にでも
書き込みます。但し、その定理が有効かどうかはまだ見えていません。
単なる使ってみたいだけと言う事もあります。

回答No.3

stomachman

そうスッキリとは行きそうにない問題で、すぐには検討できないんで、とりあえずチョコチョコとプログラムを書いて走らせてみました。No.1の回答と似たような発想で、
(1) 誰も、同じ人とは高々２回しか同じ組にならない。
という条件を付け、さらに、
(2) ある組において、３人以上が以前のコンペで同じ組だった、ということはない。
を条件としてみました。
　で、結果ですけれど、この二つの条件を付けたとき、５回はコンペができますが、６回やる方法はどうもないみたいです。（勿論、プログラムのチョンボの可能性もありますが。）

　ですから、条件を緩めなくてはいけません。どう緩めましょうか。まずは
(1') 誰も、同じ人とは高々３回しか同じ組にならない。
としましょう。それから、実際問題としてはおそらく
(3)どの二人をとっても、６回のコンペのうち少なくとも一度は一緒の組になる。
が重要ではないでしょうか。せっかくのコンペですもんね。だから今度は、(1')(2)(3)の三つを条件にしてみようかと思います。ただ、この条件では計算時間も格段に増えると予想され、コンピュータで探索するのもいつになるやら…

お礼

皆様お忙しいところ回答下さいましてありがとうございます。　感謝しております。
自分が幹事をしているので旨く年を通して
皆とあたるようにずっと考えていたんですが
どうしても２人は続けて重なってしまうのですね。
これが４組だと簡単かな？
同じ人と続けてあたるのは良しとして
うまく組を作る方法などありますでしょうか？
たとえば乱数表のようなもので、、、。
お暇な時で結構ですのでお知恵を拝借させてください
宜しくお願い致します。

回答No.2

noname#5188

なるべく重複しないようにというのは、
例えば、

Aさんの組には毎回のように
一緒にラウンドした人がいるが
他の人はあまり重複していない

というのと、

みんな平等に重複している

のとでは、どちらがなるべく重複してないのですか？

回答No.1

graphaffine

odenon909さん、今晩は。
御質問は方針を求めているのでしょうか、それとも
具体的な回答を求めているのでしょうか。後者のような気がしますが、それは簡単には行かないので、まずは方針だけ。

１２人ですから対は全部でＣ（１２，２）＝６６個あります。また、一ラウンドで４人一組ですから、一組が
含む対はＣ（４，２）＝６個、それが３組ですから
一ラウンドは１８個の対、年６回で１０８個の対となります。
少なくとも１０８－６６＝４２個の対が重複しますから、１回だけ実現される対が２４個、２回実現される対が４２個となるようなものが選べれば多分それがご希望の組合せでしょうね。

p.s.　私は趣味で似たような幾何学的問題を考えています。そちらの理論が応用できそうな気がするのでさらに
考えてみます。