グループ分けをした総当りについて
現在総当り戦の組み合わせを生成するプログラムを作っています。
1vs1の試合を想定し、各参加メンバー同士が1回づつ組み合わさる仕様です。
まず、単純に1回戦、2回戦と回ごとに順番にローテーションしてすべての組み合わせを作ることは容易に出来ました。
それから会場分けという概念を取り入れようとしました。
複数の各会場に1回ごとメンバーをグループ分けして総当りを行うのですが、
1回のうちにそのグループ内で出来る組み合わせをすべて作ってしまい、
通常の総当りより回数を減らす事を目標としています。
いろいろ考えましたが私の知力では有効な方法が思いつきませんでした。
なんとかしてアルゴリズム化したいのでどなたかご協力お願いいたします。
２０人までの総当りなら処理に１０秒かからず
２２人で１分３０秒、２４人なら５分以上・・・
２６人で途中で・・・やめた！
ちなみに、ペンティアム４、３．７Ｇ WindowsXＰです
２０人だと試合数の総当りは
２０人がそれぞれ１９試合するんで３８０ゲーム
私の場合はありえないです・・・
で、回答なんだけど、最適なアルゴリズムはわからないです。
わたしのばあいは、再帰法とか、帰納法だっけ？
このやり方でつかってます。ネットで調べれば
わかると思います。
いろいろわかりません。
会場をわけたって「総当り」の回数は減らないよね？
ルールをどこかでトーナメントに変えないと。
それから20チームの総当りって 20C2 で190じゃないのかな？？
先攻・後攻をわざわざ変えてもう１試合するのかな（野球ならだけど）
すんません。
１９０試合です・・・
＞会場をわけたって「総当り」の回数は減らないよね？
２０人の場合２つの会場にわかれて１０人ずつになって
それぞれの会場で総当りするってことかな？
それで終わりですか・・・
それなら最初20チームだった事実は全く必要なくて
単に10チームの総当り と 10チームの総当り の和 でしょうかね。
12と8に分けたって、12の総当り と 8 の総当りを別々に考えればよいのではないでしょうか？
質問が意味不明で、質問者が出てこないとこれ以上続けても無駄でしょう
私も、最初、総当たり＋トーナメントかとも思いましたが、もしかして、
１，総当たりを、複数会場で同時に行う。
２．同時に同じ人が複数の会場に出ることはない
ということでは？
メンバーが１〜４の場合、
12 13 14 23 24 34
の6通りで、2会場で行う場合、
12 13 14
34 24 23
というように。
単純に考えると、総当たりの組み合わせから、重複しないように取り出すだけのようですが、深く考えてないので問題があるかも。
よ〜く読んでみると・・・おかしい。
まず、
前提として「1vs1の試合を想定し、各参加メンバー同士が
1回づつ組み合わさる仕様」とあります。
しかし、最後に「通常の総当りより回数を減らす」とある。
対戦回数を減らせば総当りにはなりません。
逆に、「通常じゃない総当りってなんなの？」って質問
したいのですが・・・
＞いろいろ考えましたが私の知力では有効な方法が思いつきませんでした。
私も、いろいろ考えましたが私の知力では
有効な解釈が思いつきませんでした。
> 通常の総当りより回数を減らす事を目標としています。
一会場で、全試合すると１０日かかるけど
開催地を増やすことで、開催日数を減らすことができる。
という程度の意味？
会場ってもしかして・・・
コート別とかって意味じゃないか？
んじゃ、にしのさんので正解や・・
って、いうか普通の総当り組み合わせ表ですね。
ということで、私も便乗したいのですが
私の作ったプログラムですが・・・
そのもの再帰法でして、一つ一つすすんで、
だめだと戻るという方法なのですが、
２０人を超えると極端に時間がかかる。
３０人とかだと計算に１日以上かかっちゃいそうです。
やってませんけど。
Ｐ４−１．４Ｇあたりで
１〜２分ぐらいで計算終了できるアルゴリズム教えてほしい。
今は１５、１６人で試合してるけど
２０人越すこともありそうなのでよろしくお願いしたいです。
（５０人ぐらいまで対応できれば余裕でＯＫなんですけど）
実際には２０人超していても作成した表の
最初の６試合とか７試合とかしか試合は行わないのですが
同時に７箇所で試合するので
なるべく重複しない組み合わせを作りたいのです。
お願いします。
みなさまレスありがとうございます。
しばらく放置しておいてしまって申しわけありません。
まず、結論から言うとおっ様の発言された
＞一会場で、全試合すると１０日かかるけど
＞開催地を増やすことで、開催日数を減らすことができる。
＞という程度の意味？
これが最も適当です。
私の表現力が至らず皆様を困惑させてしまったようなので改めて説明いたします。
例：
同時に試合を開催できる会場がAとBの２つあるとします、１回戦ごとに各会場同じ人数が割り振られます。
メンバーを１〜８いるとします。この場合各会場に４人ずつ割り振ります。
第１日は会場Aには1,2,3,4、会場Bには5,6,7,8が割り振られたとします。
そして各会場で総当りを行います。全組み合わせは以下になります。
会場A: (1-2,3-4),(1-3,2-4),(1-4,2-3)
会場B: (5-6,7-8),(5-7,6-8),(5-8,6-7)
第２日はメンバーを入れ替えて会場Aには1,2,5,6会場Bには3,4,7,8という具合に割り振り同様に総当りをしていきます。この時すでに行った組み合わせが重複しないようにします。
会場A: (1-5,2-6),(1-6,2-5)
会場B: (3-7,4-8),(3-8,4-7)
…
このあとも同様に繰り返して、メンバー１〜８のすべての組み合わせを行います。
これによって各メンバーが１日に１試合づつしかしない総当りをすると７日までかかる計算ですが、この方法により日数を減らすのが目的です。
どうでしょう、ご理解いただけましたでしょうか。
どうぞ宜しくお願いします。
訂正
例：
〜１回戦ごとに
↓
例：
〜１日ごとに
結局、Delphi の問題ではなく論理の問題なわけですね。
また放置されるかも
＞結局、Delphi の問題ではなく論理の問題なわけですね。
ごもっともです。
単に開発環境にDelphiを使っているのでこちらで質問させていただきました。
皆様が掲示板の趣旨から外れていて板汚しであると判断なさるならば終了と致しますが…
＞日数を減らすのが目的です。
１〜８人が１つの会場で総当りやったら、
一日ですむやんけ！
＞１〜８人が１つの会場で総当りやったら、
＞一日ですむやんけ！
時間が掛からずボードゲームなど手軽な内容の大会でしたら、1日で全試合できるとおもいますが、
スポーツの大会など１試合の時間の長さやコート数の制限などで1日では全試合が
到底終わらない場合を想定しております。
| ツイート |  |