如何生成轮次置换

Question

我想制作一款足球游戏，我必须生成球队之间的所有回合。然后我有一个这样的数组

$array = array(1,2,3,4,5,6,7,8);

如何在不重复的情况下生成元素之间的所有排列。

array(1,2)
array(3,4)
array(5,6)
array(7,8)

下一次迭代

array(1,3)
array(2,4)
array(5,7)
array(6,8)

正常排列会收到这样的重复项

(1 2) (3 4) (5 6) (7 8)
(2 1) (3 4) (5 6) (7 8)

3和4已经在上一轮了。同样是5比6和7比8。

Answer 1

我使用 array_filter 来剔除重复和团队自己玩的情况。

<?php
$teams = range(1,8);

$match_permutations = array();

foreach($teams as $team1) {
    foreach($teams as $team2) {
        $match_permutations[] = array($team1, $team2);
    }
}

//var_dump($match_permutations);

$match_combinations = array_filter($match_permutations, 
    function($item) {
        if($item[0] < $item[1]) return true;
    }
);

var_dump($match_combinations);

Answer 2

如果我们有四支球队，我们可以像这样写出所有可能的比赛排列：

(1, 1) (1, 2) (1, 3) (1, 4) 
(2, 1) (2, 2) (2, 3) (2, 4) 
(3, 1) (3, 2) (3, 3) (3, 4) 
(4, 1) (4, 2) (4, 3) (4, 4)

您可以看到在对角线中镜像的重复。

我用下面的代码输出了上面的内容：

for($i=1; $i<5; $i++) {
    for($j=1; $j<5; $j++) {
        echo "($i, $j) ";
    }
    echo "\n";
}

如果我们只关心$i小于$j的对联。或者在 $i 大于 $j 的情况下，我们剔除重复项和对角线本身（团队自己玩的地方）。

function team_combinations($no_teams) {
    $combinations = array();
    for($i=1; $i<=$no_teams; $i++) {
        for($j=1; $j<=$no_teams; $j++) {
            if($i < $j)
                $combinations[] = array($i, $j);
        }
    }

    return $combinations;
}

var_export(team_combinations(4));

输出：

array (
  0 => 
  array (
    0 => 1,
    1 => 2,
  ),
  1 => 
  array (
    0 => 1,
    1 => 3,
  ),
  2 => 
  array (
    0 => 1,
    1 => 4,
  ),
  3 => 
  array (
    0 => 2,
    1 => 3,
  ),
  4 => 
  array (
    0 => 2,
    1 => 4,
  ),
  5 => 
  array (
    0 => 3,
    1 => 4,
  ),
)

Answer 3

为了完整起见（在 SO 上），这里是从 another answer 发布的代码（感谢上面 m69 的评论）：

/****************************************************************************** 
 * Round Robin Pairing Generator 
 * Author: Eugene Wee 
 * Date: 23 May 2005 
 * Last updated: 13 May 2007 
 * Based on an algorithm by Tibor Simko. 
 * 
 * Copyright (c) 2005, 2007 Eugene Wee 
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy 
 * of this software and associated documentation files (the "Software"), to deal 
 * in the Software without restriction, including without limitation the rights 
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 
 * copies of the Software, and to permit persons to whom the Software is 
 * furnished to do so, subject to the following conditions: 
 * 
 * The above copyright notice and this permission notice shall be included in 
 * all copies or substantial portions of the Software. 
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 
 * THE SOFTWARE. 
 ******************************************************************************/ 

function generateRoundRobinPairings($num_players) { 
    // Do we have a positive number of players? If not, default to 4. 
    $num_players = ($num_players > 0) ? (int)$num_players : 4; 

    // If necessary, round up number of players to nearest even number. 
    $num_players += $num_players % 2; 

    // Format for pretty alignment of pairings across rounds. 
    $format = "%0" . ceil(log10($num_players)) . "d"; 
    $pairing = "$format-$format "; 

    // Set the return value 
    $ret = $num_players . " Player Round Robin:\n-----------------------"; 

    // Generate the pairings for each round. 
    for ($round = 1; $round < $num_players; $round++) { 
        $ret .= sprintf("\nRound #$format : ", $round); 
        $players_done = array(); 

        // Pair each player except the last. 
        for ($player = 1; $player < $num_players; $player++) { 
            if (!in_array($player, $players_done)) { 
                // Select opponent. 
                $opponent = $round - $player; 
                $opponent += ($opponent < 0) ? $num_players : 1; 

                // Ensure opponent is not the current player. 
                if ($opponent != $player) { 
                    // Choose colours. 
                    if (($player + $opponent) % 2 == 0 xor $player < $opponent) { 
                        // Player plays white. 
                        $ret .= sprintf($pairing, $player, $opponent); 
                    } else { 
                        // Player plays black. 
                        $ret .= sprintf($pairing, $opponent, $player); 
                    } 

                    // This pair of players are done for this round. 
                    $players_done[] = $player; 
                    $players_done[] = $opponent; 
                } 
            } 
        } 

        // Pair the last player. 
        if ($round % 2 == 0) { 
            $opponent = ($round + $num_players) / 2; 
            // Last player plays white. 
            $ret .= sprintf($pairing, $num_players, $opponent); 
        } else { 
            $opponent = ($round + 1) / 2; 
            // Last player plays black. 
            $ret .= sprintf($pairing, $opponent, $num_players); 
        } 
    } 

    return $ret; 
}

如何生成轮次置换

How can generate rounds of permute

php

algorithm

permute