人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

【総当り組み合わせ】【PHP】
PHPでX人の総当り組み合わせを出そうと思っています。

たとえばa,b,c,d,e,fの6人総当りならば、

$team[0] = array('a-b','c-d','e-f');
$team[1] = array('a-c','b-e','d-f');
$team[2] = array('a-d','b-f','c-e');
$team[3] = array('a-e','b-d','c-f');
$team[4] = array('a-f','b-c','d-e');

という配列を返すようにしたいのですが、どのような処理が良いでしょうか?
人数は常に偶数として考えています。

よろしくお願いします。


●質問者: res01
●カテゴリ:コンピュータ ウェブ制作
✍キーワード:PHP 偶数 配列
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● SALINGER
●100ポイント ベストアンサー

このような場合の総当りの作り方がありまして、1つを固定して時計周り(もしくは反対)に回すというやり方です。

ラウンドロビントーナメントといいますでしょうか。ロジックはこちら

http://www.prm.nau.edu/prm280/tournament_round_robin.htm


PHPでの実装はそんなに難しくないと思います。

今手元にPHPの動作環境が無いので、参考までにVBAで作ったものを紹介しておきます。

http://d.hatena.ne.jp/SALINGER/20090928

◎質問者からの返答

いつもお世話になってます。

なるほど・・・そんなアルゴリズム?があるのですね。

勉強させていただきました。

PHPのスクリプトの方も書いていただいて感激です!


2 ● KeyKey
●50ポイント

初めの全ての組み合わせを取り出す繰り返しと、次の組み合わせを配列に格納する繰り返しを結合したかったのですが思いつきませんでした。

頭にアンダーバーのある変数は一時記憶として使用しているものです。

$memberを奇数にすると無限ループとなるのでご注意ください。

$member = array("a", "b", "c", "d", "e", "f");
$num = count($member);

/* --- まず全て組み合わせを配列に格納する --- */
$_i = NULL;
$_j = NULL;
for ($i = 0; $i < $num; $i++) {
if ($_i !== $i) {
for ($j = $i + 1; $j < $num; $j++) {
if ($_j !== $j) {
$tag[$i][$j] = $member[$i] . "-" . $member[$j];
}
}
$_i = $i;
}
}

/* --- 1人目の総当たり分繰り返す -- */
$m = 0;
for ($k = 1; $k < $num; $k++) {
$_tag = $tag;
$n = 0;
$i = 0;
$j = $k;
while (count($_tag) > 0) {
/* --- $iと$j番目の組み合わせを格納し残りの組み合わせからunsetする --- */
$team[$m][$n] = $tag[$i][$j];
unset($_tag[$i]);
unset($_tag[$j]);
foreach ($_tag as $key => $val) {
unset($_tag[$key][$j]);
}
/* --- 組み合わせ配列から次の組み合わせを取り出す --- */
list($i, $j) = getary($_tag);
$n++;
}
$m++;
}
print_r($team);

/* --- 2次元配列の初めのキーを取り出すだけの関数 --- */
function getary ($ary) {
foreach ($ary as $i => $val) {
foreach ($val as $j => $val2) {
return array($i, $j);
}
}
return array(0, 0);
}
◎質問者からの返答

ありがとうございます!

私も似たような感じで書いていました。


3 ● takfjt
●100ポイント

順番がばらばらですが、

このような感じでしょうか

function souatari($player) {
 $term_len = count($player) / 2;

 # 組み合わせ初期配置
 $k = 0;
 for ($i = 0; $i < $term_len; $i++) {
 $t[$i][0] = $k;
 $t[$i][1] = $k + 1;
 $k += 2;
 }

 # 1番目以外を時計回りに配列化
 $p = array();

 for ($i = 0; $i < $term_len; $i++) {
 $p[] = $t[$i][1];
 }
 for ($i = 1; $i < $term_len; $i++) {
 $p[] = $t[$term_len - $i][0];
 }

 for ($i = 0; $i < $term_len; $i++) {
 $term[0][$i] = $player[$t[$i][0]].'-'.$player[$t[$i][1]];
 }

 # 時計回りに回す
 $len = count($p);

 for ($k = 1; $k < $len; $k++) {
 $j = 0;
 for ($i = 0; $i < $term_len; $i++) {
 $t[$i][1] = $p[($j + $k) % $len];
 $j++;
 }
 for ($i = 1; $i < $term_len; $i++) {
 $t[$term_len - $i][0] = $p[($j + $k) % $len];
 $j++;
 }

 for ($i = 0; $i < $term_len; $i++) {
 $term[$k][$i] = $player[$t[$i][0]].'-'.$player[$t[$i][1]];
 }
 }

 return ($term);
}

http://www.prm.nau.edu/prm280/tournament_round_robin.htm

◎質問者からの返答

ありがとうございます!

時計回りのロジック、とても勉強になりました。

スクリプトまで書いていただいて感謝です!

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ