【総当り組み合わせ】【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');

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

よろしくお願いします。

回答の条件
  • 1人3回まで
  • 登録:2009/09/28 15:09:28
  • 終了:2009/09/28 22:16:37

ベストアンサー

id:SALINGER No.1

SALINGER回答回数3454ベストアンサー獲得回数9692009/09/28 16:48:12

ポイント100pt

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

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

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


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

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

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

id:res01

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

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

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

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

2009/09/28 22:05:42

その他の回答(2件)

id:SALINGER No.1

SALINGER回答回数3454ベストアンサー獲得回数9692009/09/28 16:48:12ここでベストアンサー

ポイント100pt

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

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

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


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

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

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

id:res01

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

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

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

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

2009/09/28 22:05:42
id:KeyKey No.2

KeyKey回答回数29ベストアンサー獲得回数42009/09/28 18:50:13

ポイント50pt

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

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

$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);
}
id:res01

ありがとうございます!

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

2009/09/28 22:09:55
id:takfjt No.3

takfjt回答回数23ベストアンサー獲得回数32009/09/28 19:23:56

ポイント100pt

順番がばらばらですが、

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

		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

id:res01

ありがとうございます!

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

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

2009/09/28 22:12:15
  • id:KeyKey
    ごめんなさい、回答にミスがありました開かないでください。
  • id:KeyKey
    回答開かれてしまったので、自分なりの正解を
    考え方はSALINGERさん、takfjtさんと同じです。

    $member = array("a", "b", "c", "d", "e", "f");
    /* --- 1番目を固定メンバーから除外 --- */
    $first = $member[0];
    array_shift($member);
    $num = count($member);

    /* --- 1番目以外を一周回すと総当たり --- */
    for ($j = 0; $j < $num; $j++) {
     $player1[] = $first;
     for ($i = 0; $i < $num; $i++) {
      if (($i % 2) === 0) {
       $player2[] = $member[$i];
      } else {
       $player1[] = $member[$i];
      }
     }
     
     foreach ($player1 as $i => $val) {
      $team[$j][$i] = $player1[$i] . "-" . $player2[$i];
     }
     /* --- (aを除いたメンバーの)1番目を取り出し1番後ろに追加 --- */
     $temp = $member[0];
     array_shift($member);
     array_push($member, $temp);
     $player1 = array();
     $player2 = array();
    }
    print_r($team);
  • id:res01
    KeyKeyさん>
    ありがとうございます。コメントに頂いたソース理解しやすいです。
    参考にさせていただきます。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません