php - 查询使 2 个得分相等的团队

Question

我有一个看起来像这样的 table 女巫:

----------------------------------------
| index | players | date       | score |
----------------------------------------
|   1   | jan     | 2013-01-13 |   5   |
----------------------------------------
|   2   | piet    | 2013-01-13 |   6   |
----------------------------------------
|   3   | klaas   | 2013-01-13 |   5   |
----------------------------------------
|   4   | kees    | 2013-01-13 |   7   |
----------------------------------------
|   5   | william | 2013-01-13 |   8   |
----------------------------------------
|   6   | john    | 2013-01-13 |   4   |
----------------------------------------

Now I want to do something tricky, in order to play the next match like the match of 2013-01-14 we would like to make 2 score equal teams.

There are 12 players every date period so on 2013-01-13 are 12 players and on 2013-01-14 there are still the same players.

They have to be divorced into 2 teams so 12 / 2 = 6. 6 man in each team. Now that is not the problem the problem is that the total score of both teams has to be equal or close to each other.

If all the scores of the 12 players is 77 then the total scores of the 2 teams have to be almost equal like this 77 / 2 = 38,5

team 1 - players 6 - total score 37

team 2 - players 6 - total score 40

In the end the query output must be like this:

-----------------------------------------------
| index | players | date       | score | team |
-----------------------------------------------
|   1   | jan     | 2013-01-13 |   5   |   1  |
-----------------------------------------------
|   2   | piet    | 2013-01-13 |   6   |   1  |
-----------------------------------------------
|   3   | klaas   | 2013-01-13 |   8   |   1  |
-----------------------------------------------
|   4   | kees    | 2013-01-13 |   7   |   1  |
-----------------------------------------------
|   5   | william | 2013-01-13 |   5   |   1  |
-----------------------------------------------
|   6   | john    | 2013-01-13 |   6   |   1  |
-----------------------------------------------
|   7   | gerrit  | 2013-01-13 |   6   |   2  |
-----------------------------------------------
|   8   | maartje | 2013-01-13 |   6   |   2  |
-----------------------------------------------
|   9   | shara   | 2013-01-13 |   8   |   2  |
-----------------------------------------------
|  10   | els     | 2013-01-13 |   7   |   2  |
-----------------------------------------------
|  11   | allen   | 2013-01-13 |   5   |   2  |
-----------------------------------------------
|  12   | steven  | 2013-01-13 |   8   |   2  |
-----------------------------------------------

and

-----------------------------------------------
|  team     | score    | date       | players |
-----------------------------------------------
|  Team 1   | 37       | 2013-01-13 |    6    |
-----------------------------------------------
|  Team 2   | 40       | 2013-01-13 |    6    |
-----------------------------------------------

With some inspiration of #Danack I made this:

$difference = 10;
$team_smnstlln = array();
for($q=0; $q<1000; $q++){
    
    $players = array();
    
    $team_smnstlln[$q] = array(
                                'team1' => array(),
                                'team2' => array(),
                                'total' => 0
                              );
    
    $count1 = 0;
    for($w=0; $w<6; $w++){
        $player = pick_random(true);
        $score1 = $team_smnstlln[$q]['team1'][$player] = $data[$player]['score'];
        $count1 = $count1 + $score1;
    }
    
    $count2 = 0;
    for($w=6; $w<12; $w++){
        $player = pick_random(true);
        $score2 = $team_smnstlln[$q]['team2'][$player] = $data[$player]['score'];
        $count2 = $count2 + $score2;
    }
    
    if($count1 > $count2){
        $total = $count1 - $count2;
    }
    elseif($count2 > $count1){
        $total = $count2 - $count1;
    }
    else{
        $total = 0;
    }
    
    $team_smnstlln[$q]['total'] = $total;
    
    if($team_smnstlln[$q]['total'] == 0){
        $difference = 0;
        $winner = $q;
        break;
    }
    elseif($team_smnstlln[$q]['total'] < $difference){
        $difference = $team_smnstlln[$q]['total'];
        $winner = $q;
    }
    
}

echo "Kleinst gekozen set met score verschil van $difference punten. array $winner is gekozen<br>";

$team1 = $team_smnstlln[$winner]['team1'];
$team2 = $team_smnstlln[$winner]['team2'];

print_r($team1);
print_r($team2);

// random player picker

function pick_random($gonogo){
    
    global $players;
    
    $go = true;
    $total_players = 11;
    
    while($go){
        
        $player = rand(0, $total_players);
        
        if(!in_array($player, $players)){
            $players[] = $player;
            $go = false;
        }
        
    }
    
    return $player;
    
}

此代码运行 1000 个不同的团队设置。当达到 0 分差时，它将停止并回显最佳平等队比赛。否则当没有 0 差异时，它将返回最低结果

Answer 1

正如 moonwave99 所说，在 PHP 中执行此操作比在 SQL 中执行此操作要好得多。

问题在于这是一个很难解决的问题。您可以通过将您的问题重新问为:

“一个队的 6 名球员和另一队的 6 名球员的什么组合得分差异最小？”

从 12 名球员中选出 6 名球员的组合数量为(12!/6!)或 665,280 种组合，每种组合都需要计算分数差。

您需要遍历所有可能的组合，并计算每个组合的分数以找到“最佳”组合。

//An array to record whether each player has already been selected for a combination
$playersChosen = array();

//Initialise the array
for($x=0 ; $x<12 ; $x++){
    $playersChosen[$x] = FALSE;
}

//Need to store lowest score somewhere - and have a flag for the first calculation
$lowestScore = FALSE;


chooseAnotherPlayer(6, 0);

//$GLOBALS['bestCombination'] - will now contain the best combination of players.


//Recursive function that either:
//goes through each player in turn and then calls itself or 
//calculates the 'score' when all the players are chosen for one team
//$playersToChoose - how many players left to choose.
//$minimumPlayerNumber - index to start searching for players not yet chosen - as the choice,  3 + 5 is identical to 5 + 3
function chooseAnotherPlayer($playersToChoose, $minimumPlayerNumber){

    //We have 6 pl
    if($playersToChoose == 0){
        //Calculate Score from which players are selected in $GLOBALS['playersChosen']
        if($lowestScore === FALSE ||
            $score < $lowestScore){
            $GLOBALS['bestCombination'] = $GLOBALS['playersChosen'];  //Arrays are copied by value, not reference
//So this saves a snapshot of the best selection.
        }
        return;
    }

    //Go through each of the players
    for($x=$minimumPlayerNumber ; $x<12; $x++){
        //Select them if they're available
        $playerAvailable = selectPlayer($x);
        if($playerAvailable == TRUE){
                    //Pick another player
            chooseAnotherPlayer($playersToChose - 1, $x + 1);
                    //Release this player, so he's available for other combinations
            unselectPlayer($x);
        }
    }
}

function selectPlayer($x){
    if($GLOBALS['playersChosen'][$x] == TRUE){
        //Player has already been selected in this combination.
        return FALSE;
    }

    return TRUE;
}

如果您不介意花几秒钟来处理该代码将完全解决您的问题。但是，如果您需要快速完成，最好只是随机选择团队、评估“分数”并进行足够多的迭代以获得合理的结果。

$playersChosen = array();

resetArray();

$playersToChose = 6;
$lowestScore = FALSE;

for($n=0 ; $n<10000 ; $n++){
    chooseAnotherPlayers(6);
    resetArray();
}

function chooseAnotherPlayer($playersToChoose){

    if($playersToChoose == 0){
        //Calculate Score from which players are selected in $GLOBALS['playersChosen']
        if($lowestScore === FALSE ||
            $score < $lowestScore){
            $GLOBALS['bestCombination'] = $GLOBALS['playersChosen'];
            return;
        }
    }

    selectPlayerAtRandom($x);
    chooseAnotherPlayer($playersToChose - 1);
}

function selectPlayer($x){

    $playerSelected = FALSE;

    while($playerSelected == FALSE){

        $x = rand(0, 12 - 1);

        if($GLOBALS['playersChosen'][$x] == FALSE){
            $GLOBALS['playersChosen'][$x] = TRUE;
            return $x;
        }    
    }

}

function resetArray(){
    for($x=0 ; $x<12 ; $x++){
        $GLOBALS['playersChosen'][$x] = FALSE;
    }
}

除非您需要让团队精确匹配，否则由于标准偏差和分布背后的数学原理，即使只覆盖了一小部分不同组合，这也可能会为您提供非常接近的结果。

您可以通过“经验法则”计算出可接受的总分差是多少，并进行搜索直到找到满足该条件的玩家组合或运行最大搜索时间(可能会生成搜索超时的警报，并且匹配不均匀)。