PHP: Optimizing array iteration

Question

i am working on an algorithm for sorting teams based on highest number of score. Teams are to be generated from a list of players. The conditions for creating a team is

• It should have 6 players.
• The collective salary for 6 players must be less than or equal to 50K.
• Teams are to be generated based on highest collective projection.

What i did to get this result is generate all possibilities of team then run checks on them to exclude those teams that have more than 50K salary and then sort the remainder based on projection. But generating all the possibilities takes a lot of time and sometimes it consume all the memory. For a list of 160 players it takes around 90 seconds. Here is the code

$base_array = array();
$query1 = mysqli_query($conn, "SELECT * FROM temp_players  ORDER BY projection DESC");
while($row1 = mysqli_fetch_array($query1))
{
    $player = array();
    $mma_id = $row1['mma_player_id'];
    $salary = $row1['salary'];
    $projection = $row1['projection'];
    $wclass = $row1['wclass'];

    array_push($player, $mma_id);
    array_push($player, $salary);
    array_push($player, $projection);
    array_push($player, $wclass);

    array_push($base_array, $player);
}


$result_base_array = array();
$totalsalary = 0;

for($i=0; $i<count($base_array)-5; $i++)
{
    for($j=$i+1; $j<count($base_array)-4; $j++)
    {
        for($k=$j+1; $k<count($base_array)-3; $k++)
        {
            for($l=$k+1; $l<count($base_array)-2; $l++)
            {
                for($m=$l+1; $m<count($base_array)-1; $m++)
                {
                    for($n=$m+1; $n<count($base_array)-0; $n++)
                    {
                        $totalsalary = $base_array[$i][1]+$base_array[$j][1]+$base_array[$k][1]+$base_array[$l][1]+$base_array[$m][1]+$base_array[$n][1];
                        $totalprojection = $base_array[$i][2]+$base_array[$j][2]+$base_array[$k][2]+$base_array[$l][2]+$base_array[$m][2]+$base_array[$n][2];
                        if($totalsalary <= 50000)
                        {
                            array_push($result_base_array, 
                            array($base_array[$i], $base_array[$j], $base_array[$k], $base_array[$l], $base_array[$m], $base_array[$n],
                            $totalprojection, $totalsalary)
                            );

                        }
                    }
                }
            }
        }

    }
}

usort($result_base_array, "cmp");

And the cmp function

function cmp($a, $b) {
    if ($a[6] == $b[6]) {
        return 0;
    }
    return ($a[6] < $b[6]) ? 1 : -1;
}

Is there anyway to reduce the time it takes to do this task, or any other workaround for getting the desired number of teams

Regards

Answer 1

Because number of elements in array can be very big (for example 100 players can generate 1.2*10^9 teams), you can't hold it in memory. Try to save resulting array to file by parts (truncate array after each save). Then use external file sorting.

It will be slow, but at least it will not fall because of memory.

If you need top n teams (like 10 teams with highest projection) then you should convert code that generates result_base_array to Generator, so it will yield next team instead of pushing it into array. Then iterate over this generator. On each iteration add new item to sorted resulted array and cut redundant elements.