PHP-How To Pair Up items in Array based on conditi

问题:

How can I pair up items in an array? Let's say I have an array of Fighters. And I want to pair them up based on their Weights. Fighters with closest weights should be paired as the Best Match. But if they are in the same team they shouldn't be paired.

• **---Team 1--**
• Fighter A Weight is 60
• Fighter B Weight is 65
• **--Team 2--**
• Fighter C Weight is 62
• Fighter D Weight is 60
• **--Team 3--**
• Fighter E Weight is 64
• Fighter F Weight is 66

Output:

• Fighter A VS Fighter D
• Fighter B VS Fighter F
• Fighter C VS Fighter E

I've been researching for this topic and found something similar but not quite: Random But Unique Pairings, with Conditions

Would really appreciate some help. Thanks in advance!

回答1:

I liked your question a lot, so I made a full robust version of it.

<?php

    header("Content-type: text/plain");
    error_reporting(E_ALL);

    /**
     * @class            Fighter
     * @property $name   string
     * @property $weight int
     * @property $team   string
     * @property $paired Fighter  Will hold the pointer to the matched Fighter
     */
    class Fighter {
        public $name;
        public $weight;
        public $team;
        public $paired = null;

        public function __construct($name, $weight, $team) {
            $this->name   = $name;
            $this->weight = $weight;
            $this->team   = $team;
        }
    }

    /**
     * @function sortFighters()
     *
     * @param $a Fighter
     * @param $b Fighter
     *
     * @return int
     */
    function sortFighters(Fighter $a, Fighter $b) {
        return $a->weight - $b->weight;
    }

    $fighterList = array(
        new Fighter("A", 60, "A"),
        new Fighter("B", 65, "A"),
        new Fighter("C", 62, "B"),
        new Fighter("D", 60, "B"),
        new Fighter("E", 64, "C"),
        new Fighter("F", 66, "C")
    );
    usort($fighterList, "sortFighters");

    foreach ($fighterList as $fighterOne) {
        if ($fighterOne->paired != null) {
            continue;
        }
        echo "Fighter $fighterOne->name vs ";
        foreach ($fighterList as $fighterTwo) {
            if ($fighterOne->team != $fighterTwo->team && $fighterTwo->paired == null) {
                echo $fighterTwo->name . PHP_EOL;
                $fighterOne->paired = $fighterTwo;
                $fighterTwo->paired = $fighterOne;
                break;
            }
        }

    }

1. First, the fighters are kept in classes, which makes it easier to assign properties to them (if you haven't done so yourself, I urge you to do!)
2. Make an array of fighters, and assign them names, weights and teams.
3. sort the array by weight (using usort() and a sorting function sortFighters() to sort by the weight property of each element.
4. Iterate through the array and match based on:
   1. Fighter one is not already matched
   2. Fighter two is not on the same team as Fighter one
   3. Fighter two is not already matched
5. When a match is found, store the object pointer of each matching fighters to each other (So it's not null anymore, plus you can access each of fighters' pairs by going to $fighterVariable->paired)
6. Finally, print the result.

回答2:

This is just extension of Truth's answer based on comments:

The first thing I'd do differently is basic keeping trace players.

$unassignedPlayers = $fighterList;

Than the algorithm would work in the way: prepare list of teams (if you're using database, use SELECT DISTINCT or GROUP BY teams.id):

$teams = array();
foreach( $fighterList as $fighter){
    $teams[] = $figter->team;
}
$teams = array_unique( $teams);

Next we'll need method that will split array of fighters (let's say, we have teams {A,A,B,B,C,C} we want to split that into {A,A}, {B,B,C,C}):

// Don't use string type declaration, it's just ilustrating
function splitFighters( array $input, string $team){
    $inteam = array();
    $outteam = array();
    foreach( $input as $fighter){
        if( $figter->team == $team){
           $inteam[] = $fighter;
        } else {
           $outteam[] = $fighter;
        }
    }

    return array( $inteam, $outteam);
}

Now that we do have that, we may create function that will sort team members:

function assignFighters( array &$input, array $teams, array &$output){
    // Nothing to work with?
    if( !count( $input)){
        return true;
    }

    // No team left and still unassigned players, that fatal error
    if( !cont( $teams)){
        throw new Exception( 'Unassigned players occurred!');
    }

    // Shift team
    $team = array_shift( $teams);

    // Split into in and out team
    list( $inteam, $outteam) = splitFighters( $input, $team);

    // Inteam is already empty (let's say all players were assigned before)
    // Just go deeper (where's DiCaprio?)
    if( !count( $inteam) && count( $teams)) {
        return assignFighters( $input, $teams, $output)
    }

    // There're unassigned and nonassignable players in this team
    // This is error and we'll have to deal with it later
    if( !count($outteam)){
        $input = $inteam; // Propagate unassigned players to main
        return false;
    }

    // Sort both teams by fighters weight
    // Uses Truth's comparison function
    usort($inteam, "sortFighters");
    usort($outteam, "sortFighters");

    // Fig = Fighter
    while( $fig1 = array_shift( $inteam)){
         // Are there any players to work with
         if( !count( $outteam)){
             array_unshift( $inteam, $fig1);
             $input = $inteam; // Propagate unassigned players to main
             return false;
         }

         // Assign players to each other
         $fig2 = array_shift( $outteam);
         $fig1->paired = $fig2;
         $fig2->paired = $fig1;

         // This will propagate players to main nicely
         $output[] = $fig1;
         $output[] = $fig2;
    }

    // Still here? Great! $inteam is empty now
    // $outteam contains all remaining players
    $input = $outteam;

    return assignFighters( $input, $teams,$output);
}

Until this point you could use Truth's algorithm, but this should have better weight matching and represents what you intend more clearly but anyway now comes $unassignedPlayers into work:

$assignedPlayers = array();
$state = assignFighters( $unassignedPlayers, $teams, $assignedPlayers);

// Note:
$state === !(bool)count($unassignedPlayers)
// should evaluate as true, otherwise I'm having an error in algorithm

So what now... If you have $state === false resp. count( $unassignedPlayers) > 0 something went wrong and we need to apply some magic. How will that magic work:

// Keep the trace of swapped players so we don't end up in endless loop
$swappedPlayers = array();

// Browse all unassigned players
while( $fig1 = array_shift( $unassignedPlayers)){
    // Store as swapped
    $swappedPlayers[] = $fig1;

    // At first check whether there's not unassigned player in the different team
    // this shouldn't occur in first iteration (all fighters should be from one team
    // in the beginning) but this is most effective part of this method
    foreach( $unassignedPlayers as $key => $fig2){
       if( $fig2->team != $fig1->team){
            $fig1->pair = $fig2;
            $fig2->pair = $fig1;
            continue;
       }
    }

    // No luck, normal magic required
    list( $inteam, $outteam) = splitFighters( $assignedPlayers, $fig1->team);

    $fig2 = null; // I like my variables initialized, this actually quite important

    // Now select someone from $outteam you will want to swap fights with.
    // You may either iterate trough all players until you find best weight
    // match or select it random, or whatever, I'll go with random,
    // it's your job to implement better selection
    $i = 1000;  // Limit iterations
    while(($i--) > 1){
       $key1 = array_rand( $outteam, 1);
       if( $outteam[$key]->team == $fig1->team){
          continue; // No point in swapping fit team member
       }

       // No recursive swaps
       if( in_array( $outteam[$key], $swappedPlayers)){
          continue;
       }

       // This may speed things really up:
       // That means we'll get rid of 2 players due to foreach loop at the beggining
       // However I'm not sure how this condition will really work
       if( $outteam[$key]->pair->team == $fig1->team){
          continue;
       }

       // Store matched fighter
       $fig2 = $outteam[$key];

       // Unset pair from another fighter
       $fig2->pair->pair = null;

       // Find the pair in $assignedPlayers and move it to $unassignedPlayers
       $key = array_search( $fig2->pair, $assignedPlayers);
       if( $key === false){
           throw new Exception( 'Cannot find pair player');
       }
       unset( $assignedPlayers[$key]);
       $unassignedPlayers[] = $fig2->pair;
       $swappedPlayers[] = $fig2->pair;

       // Remove pair from self
       $fig2->pair = null;
       $swappedPlayers[] = $fig2;
       break; // hh, try forgetting this one :)
    }

    // This shouldn't be happening
    if( $fig2 === null){
         throw new Exception( 'Didn\'t find good match in 1000 iterations.');
    }

    // Ok now just make matches as go to the next iteration
    $fig1->pair = $fig2;
    $fig2->pair = $fig1;

    // And store those
    $assignedPlayers[] = $fig1;
    $assignedPlayers[] = $fig2;
}

_{I've written all this out of my head (it was challenge), test it and leave notes in comments please :)}

回答3:

Sort the array by weight. You will then have pairs of weights that are close to each other.