Back

校运会田径比赛组队算法

首先接到的需求是这样的:

  • 第一个要求,跑道上的每一组(8人)里,学生班级不能有重复
  • 第二个要求,出现最后一组不足5人的情况,需要和倒数第二组进行混排使每一组队伍不少于4人
  • 第三个要求,除了最后两组以外,其他小组尽量满员
  • 第四个要求,没满员的队伍,学生必须站居中站开

首先看到第一个和第二个和第三个要求写出了大概下面这个算法
首先想到的是必须把报名人数的多的班级给先排组了,不然会导致后面班级不够无法排满的情况

组队算法:

$grouping_Sporter=function($c_u){
    $classNoP=array();
    $sporter_team=array();
    $single_Sporter=array();
    $total=0;
    $TeamNum=8;
    $TeamMin=5;

    foreach($c_u as $key => $value)
        $classNoP[$key]=count($c_u[$key]);

    foreach ($c_u as $key => $value) 
        $total+=count($c_u[$key]);
    //判断是否需要调整倒数末尾两排人的分组
    if($total%$TeamNum<=$TeamMin&&$total%$TeamNum!=0){
        $Selected_class=array_rand($c_u,$TeamNum+$total%$TeamNum);

        foreach ($Selected_class as $key => $value){ 
            shuffle($c_u[$value]);
            array_push($single_Sporter, array_pop($c_u[$value]));
        }
        foreach ($Selected_class as $key => $value) 
            if(count($c_u[$value])>0)
                $classNoP[$value]=count($c_u[$value]);
            else
                unset($classNoP[$value]);
    }
    //排队核心,将多人的班级进行优先排序
    while(count($classNoP)>0)
    {
        $Selected_Sporter=array();
        $Selected_class=array();
        
        //shuffle($classNoP);
        asort($classNoP);
        $classNoPKEY=array_keys($classNoP);
        $$TeamNum=count($classNoPKEY)>$TeamNum?$TeamNum:count($classNoPKEY);
        for($i=$$TeamNum;$i>0;$i--)
            array_push($Selected_class,array_pop($classNoPKEY));

        foreach ($Selected_class as $key => $value) {
            $c=&$c_u[$value];
            shuffle($c);
            array_push($Selected_Sporter,array_pop($c));
        }

        array_push($sporter_team,$Selected_Sporter);
        foreach ($Selected_class as $key => $value) {
            if(count($c_u[$value])>0)
                $classNoP[$value]=count($c_u[$value]);
            else
                unset($classNoP[$value]);
                
        }

    }
    
    //调整两排人分组
    $t=count($single_Sporter);
    while(count($single_Sporter)>0)
    {
        $Selected_Sporter=array();
        for($i=floor($t/2)+$t%2;$i>0;$i--)
            if(($c=array_pop($single_Sporter))!=null)
                array_push($Selected_Sporter,$c);
            else
                break;
        $sporter_team[]=$Selected_Sporter;
    }
    
    return $sporter_team;
};

组队居中

然后第四个要求,只需要对每组进行居中重排就行了

$group_offset=function($c_u)
{
    $TeamNum=8;
    $TeamMin=5;
    foreach ($c_u as $key => $value) {
        if(count($c_u[$key])==$TeamNum) continue;
        $offset=floor($TeamNum/2-count($value)/2);
        $temp=array();
        foreach ($c_u[$key] as $k => $v) 
            $temp[$offset++]=$v;
        $c_u[$key]=$temp;
    }
    return $c_u;
};

其实只要对最后两组排序,基本就可以,因为有第三个要求限制


测试

然后再写几个额外的代码进行测试下

class doing
{
    private $parameter=null;
    private $functions=array();
    public function setParameter($_parameter)
    {
        $this->parameter=$_parameter;
        return $this;
    }
    public function setFunctions($_functions)
    {
        if(is_array($_functions))
            foreach ($_functions as $key => $value)
                $this->functions[]=$value;
        else
            $this->functions[]=$_functions;
        return $this;
    }
    public function run()
    {
        //if($parameter&&count($this->functions)>=1)
            return $this->runtest();
        //else return null;
    }
    public function run_once()
    {
        $ret=$this->runtest();
        $this->functions=array();
        return $ret;
    }
    private function runtest()
    {
        foreach($this->functions as $key => $value)
            $this->parameter=$value($this->parameter);
        return $this->parameter;

    }
    public function deBug()
    {
        echo("parameter:\r\n");
        print_r($this->parameter);
        echo("functions:\r\n");
        print_r($this->functions);
    }
}
$do=new doing();
$debugPrint=function($c_u)
{
    echo "<pre>";
    print_r($c_u);
    echo "</pre>";
    return $c_u;
};


$loadClassFromRandom=function($c_u){
    $ClassNum=20;
    $StudentMaxNum=5;
    $StudentMinNum=2;
    for($c=$ClassNum;$c>0;$c--)
    {
        $class=array();
        for($u=rand($StudentMinNum,$StudentMaxNum);$u>=0;$u--)
            $class[]='CLASS_'.$c.'||USER_'.$u;
        $c_u['CLASS_'.$c]=$class;
    }
    return $c_u;
};

require_once("sports_autoGroup.php");

//$runFunc[]=$init_class_user;

$runFunc[]=$loadClassFromRandom;
$runFunc[]=$debugPrint;
$runFunc[]=$grouping_Sporter;
$runFunc[]=$group_offset;

$do=new doing();
$sporter_team=$do->setParameter(array())->setFunctions($runFunc)->run_once();


//输出结果
echo "<pre>";
print_r($sporter_team);
echo "</pre>";

然后我就放一个输出结果参考:

报名数据:

Array (
    [CLASS_20] => Array
        (
            [0] => CLASS_20||USER_5
            [1] => CLASS_20||USER_4
            [2] => CLASS_20||USER_3
            [3] => CLASS_20||USER_2
            [4] => CLASS_20||USER_1
            [5] => CLASS_20||USER_0
        )

    [CLASS_19] => Array
        (
            [0] => CLASS_19||USER_5
            [1] => CLASS_19||USER_4
            [2] => CLASS_19||USER_3
            [3] => CLASS_19||USER_2
            [4] => CLASS_19||USER_1
            [5] => CLASS_19||USER_0
        )

    [CLASS_18] => Array
        (
            [0] => CLASS_18||USER_5
            [1] => CLASS_18||USER_4
            [2] => CLASS_18||USER_3
            [3] => CLASS_18||USER_2
            [4] => CLASS_18||USER_1
            [5] => CLASS_18||USER_0
        )

    [CLASS_17] => Array
        (
            [0] => CLASS_17||USER_5
            [1] => CLASS_17||USER_4
            [2] => CLASS_17||USER_3
            [3] => CLASS_17||USER_2
            [4] => CLASS_17||USER_1
            [5] => CLASS_17||USER_0
        )

    [CLASS_16] => Array
        (
            [0] => CLASS_16||USER_3
            [1] => CLASS_16||USER_2
            [2] => CLASS_16||USER_1
            [3] => CLASS_16||USER_0
        )

    [CLASS_15] => Array
        (
            [0] => CLASS_15||USER_2
            [1] => CLASS_15||USER_1
            [2] => CLASS_15||USER_0
        )

    [CLASS_14] => Array
        (
            [0] => CLASS_14||USER_5
            [1] => CLASS_14||USER_4
            [2] => CLASS_14||USER_3
            [3] => CLASS_14||USER_2
            [4] => CLASS_14||USER_1
            [5] => CLASS_14||USER_0
        )

    [CLASS_13] => Array
        (
            [0] => CLASS_13||USER_2
            [1] => CLASS_13||USER_1
            [2] => CLASS_13||USER_0
        )

    [CLASS_12] => Array
        (
            [0] => CLASS_12||USER_5
            [1] => CLASS_12||USER_4
            [2] => CLASS_12||USER_3
            [3] => CLASS_12||USER_2
            [4] => CLASS_12||USER_1
            [5] => CLASS_12||USER_0
        )

    [CLASS_11] => Array
        (
            [0] => CLASS_11||USER_3
            [1] => CLASS_11||USER_2
            [2] => CLASS_11||USER_1
            [3] => CLASS_11||USER_0
        )

    [CLASS_10] => Array
        (
            [0] => CLASS_10||USER_3
            [1] => CLASS_10||USER_2
            [2] => CLASS_10||USER_1
            [3] => CLASS_10||USER_0
        )

    [CLASS_9] => Array
        (
            [0] => CLASS_9||USER_3
            [1] => CLASS_9||USER_2
            [2] => CLASS_9||USER_1
            [3] => CLASS_9||USER_0
        )

    [CLASS_8] => Array
        (
            [0] => CLASS_8||USER_5
            [1] => CLASS_8||USER_4
            [2] => CLASS_8||USER_3
            [3] => CLASS_8||USER_2
            [4] => CLASS_8||USER_1
            [5] => CLASS_8||USER_0
        )

    [CLASS_7] => Array
        (
            [0] => CLASS_7||USER_3
            [1] => CLASS_7||USER_2
            [2] => CLASS_7||USER_1
            [3] => CLASS_7||USER_0
        )

    [CLASS_6] => Array
        (
            [0] => CLASS_6||USER_4
            [1] => CLASS_6||USER_3
            [2] => CLASS_6||USER_2
            [3] => CLASS_6||USER_1
            [4] => CLASS_6||USER_0
        )

    [CLASS_5] => Array
        (
            [0] => CLASS_5||USER_5
            [1] => CLASS_5||USER_4
            [2] => CLASS_5||USER_3
            [3] => CLASS_5||USER_2
            [4] => CLASS_5||USER_1
            [5] => CLASS_5||USER_0
        )

    [CLASS_4] => Array
        (
            [0] => CLASS_4||USER_4
            [1] => CLASS_4||USER_3
            [2] => CLASS_4||USER_2
            [3] => CLASS_4||USER_1
            [4] => CLASS_4||USER_0
        )

    [CLASS_3] => Array
        (
            [0] => CLASS_3||USER_3
            [1] => CLASS_3||USER_2
            [2] => CLASS_3||USER_1
            [3] => CLASS_3||USER_0
        )

    [CLASS_2] => Array
        (
            [0] => CLASS_2||USER_3
            [1] => CLASS_2||USER_2
            [2] => CLASS_2||USER_1
            [3] => CLASS_2||USER_0
        )

    [CLASS_1] => Array
        (
            [0] => CLASS_1||USER_5
            [1] => CLASS_1||USER_4
            [2] => CLASS_1||USER_3
            [3] => CLASS_1||USER_2
            [4] => CLASS_1||USER_1
            [5] => CLASS_1||USER_0
        )

) 

排队结果:

Array (
    [0] => Array
        (
            [0] => CLASS_5||USER_0
            [1] => CLASS_19||USER_5
            [2] => CLASS_1||USER_3
            [3] => CLASS_14||USER_2
            [4] => CLASS_8||USER_4
            [5] => CLASS_12||USER_4
            [6] => CLASS_6||USER_3
            [7] => CLASS_17||USER_5
        )

    [1] => Array
        (
            [0] => CLASS_1||USER_5
            [1] => CLASS_20||USER_1
            [2] => CLASS_18||USER_3
            [3] => CLASS_19||USER_3
            [4] => CLASS_5||USER_1
            [5] => CLASS_11||USER_1
            [6] => CLASS_3||USER_0
            [7] => CLASS_10||USER_1
        )

    [2] => Array
        (
            [0] => CLASS_9||USER_0
            [1] => CLASS_12||USER_2
            [2] => CLASS_4||USER_2
            [3] => CLASS_8||USER_3
            [4] => CLASS_14||USER_3
            [5] => CLASS_17||USER_1
            [6] => CLASS_6||USER_0
            [7] => CLASS_16||USER_3
        )

    [3] => Array
        (
            [0] => CLASS_19||USER_0
            [1] => CLASS_18||USER_1
            [2] => CLASS_20||USER_5
            [3] => CLASS_5||USER_2
            [4] => CLASS_1||USER_4
            [5] => CLASS_14||USER_0
            [6] => CLASS_2||USER_0
            [7] => CLASS_15||USER_2
        )

    [4] => Array
        (
            [0] => CLASS_3||USER_3
            [1] => CLASS_12||USER_1
            [2] => CLASS_9||USER_2
            [3] => CLASS_11||USER_0
            [4] => CLASS_6||USER_4
            [5] => CLASS_17||USER_2
            [6] => CLASS_4||USER_1
            [7] => CLASS_8||USER_1
        )

    [5] => Array
        (
            [0] => CLASS_16||USER_0
            [1] => CLASS_20||USER_0
            [2] => CLASS_10||USER_2
            [3] => CLASS_18||USER_5
            [4] => CLASS_19||USER_2
            [5] => CLASS_1||USER_0
            [6] => CLASS_5||USER_4
            [7] => CLASS_7||USER_2
        )

    [6] => Array
        (
            [0] => CLASS_6||USER_1
            [1] => CLASS_12||USER_0
            [2] => CLASS_2||USER_3
            [3] => CLASS_15||USER_0
            [4] => CLASS_9||USER_1
            [5] => CLASS_4||USER_3
            [6] => CLASS_11||USER_2
            [7] => CLASS_14||USER_1
        )

    [7] => Array
        (
            [0] => CLASS_1||USER_1
            [1] => CLASS_16||USER_1
            [2] => CLASS_20||USER_2
            [3] => CLASS_10||USER_0
            [4] => CLASS_18||USER_2
            [5] => CLASS_19||USER_1
            [6] => CLASS_5||USER_5
            [7] => CLASS_7||USER_1
        )

    [8] => Array
        (
            [0] => CLASS_8||USER_0
            [1] => CLASS_3||USER_1
            [2] => CLASS_17||USER_0
            [3] => CLASS_13||USER_2
            [4] => CLASS_10||USER_3
            [5] => CLASS_6||USER_2
            [6] => CLASS_12||USER_5
            [7] => CLASS_15||USER_1
        )

    [9] => Array
        (
            [0] => CLASS_20||USER_4
            [1] => CLASS_18||USER_4
            [2] => CLASS_19||USER_4
            [3] => CLASS_5||USER_3
            [4] => CLASS_7||USER_0
            [5] => CLASS_16||USER_2
            [6] => CLASS_4||USER_0
            [7] => CLASS_1||USER_2
        )

    [10] => Array
        (
            [0] => CLASS_9||USER_3
            [1] => CLASS_14||USER_4
            [2] => CLASS_11||USER_3
            [3] => CLASS_13||USER_0
            [4] => CLASS_17||USER_4
            [5] => CLASS_2||USER_1
            [6] => CLASS_3||USER_2
            [7] => CLASS_8||USER_2
        )

    [11] => Array
        (
            [1] => CLASS_2||USER_2
            [2] => CLASS_4||USER_4
            [3] => CLASS_7||USER_3
            [4] => CLASS_8||USER_5
            [5] => CLASS_12||USER_3
        )

    [12] => Array
        (
            [1] => CLASS_13||USER_1
            [2] => CLASS_14||USER_5
            [3] => CLASS_17||USER_3
            [4] => CLASS_18||USER_0
            [5] => CLASS_20||USER_3
        )

)
Submit
    Miao
    Miao  2016-03-01, 13:33

    好像很不错的样子

    Melody
    Melody  2016-02-19, 16:58

    可能比较冗余