从数组PHP中获取所有组合

Question

我只是需要你的帮助。我正在使用PHP构建一个关于学术咨询的系统。基本上我需要一个关于如何实现系统的主要功能的算法。主要思想是在一个数组中有一个课程列表，我需要从这个列表中获得所有可能的组合。每个课程都有一个指定其大小的单位/编号。算法应该根据特定的大小进行组合。

例如。

English - 1
Math - 3
Algebra - 3
History 3
Computer(lec) - 2
Computer(lab) - 1

最大尺寸= 9。

因此，算法应该在不超过大小限制的情况下获得所有组合。

所以结果可能是这样的。

(Math , Algebra , History ) the size is equal to 9
(History , Computer(lec), Computer(lab), Algebra)
(English , Computer(lec), Computer(lab), Algebra)

差不多吧。谢谢。我只是需要你的建议。

Answer 1

试试这个：

$courses=array('English','Math','Algebra','History','Computer(lec)');
$sizes = array('1','3','3','3','2');
//maximum 6 hours
$limit=9;
//minimum number of 3 courses
$minimum=3;

$possible= array();
function get_comb($previous, $depth){

    global $courses;
    $count=count($courses);
    global $possible;
    global $sizes;
    global $limit;
    global $minimum;

    if ($depth>$count){
        $size_of_course=0;
        foreach($previous as $nr=>$course){
            if($course !== 0){
                $size_of_course+=$sizes[$nr];
            }
            else{
                //remove zeros
                unset($previous[$nr]);
            }


        }
        if ($size_of_course<=$limit&&count($previous)>=$minimum){

           $possible[]=$previous;

        }


        return;
    }


    //either you have this course...
    get_comb(array_merge($previous,array($courses[$depth-1])),$depth+1);
    //or you dont..
    get_comb(array_merge($previous,array(0)),$depth+1);


}
get_comb(array(),1);


//output
echo '<pre>';
var_dump($possible);

在前面的变量中，过程相加，而函数进行递归。

说明:首先，我计算所有可能的组合。为了做到这一点，我把课程看作是老虎机：

whether you take the course or not, possibilities:
course a    course b
yes         yes
yes         no
no          yes
no          no

这是通过函数的这一部分完成的。它是一个递归函数，所以它在函数中调用自己：

function get_comb($previous, $depth){       
   //either you have this course...
   get_comb(array_merge($previous,array($courses[$depth-1])),$depth+1);
   //or you dont..
   get_comb(array_merge($previous,array(0)),$depth+1);
}
get_comb(array(),1);

假设是这样：

$courses=array('course a','course b');

递归函数调用将如下所示(0表示您不需要学习该课程)：http://img43.imageshack.us/img43/5688/flowdiagram.png

在那之后，如果它们符合要求，我将可能性保存在$possible中:因为depth=3和count=2，$depth>$count，所以这部分代码开始发挥作用：

if ($depth>$count){
    $size_of_course=0;
    foreach($previous as $nr=>$course){
        if($course !== 0){
            //the index of $previous is the same as in $courses and $sizes, so
            //$previous[1],$courses[1],$sizes[1] is logicaly referring to the same course
            //add up all sizes of the courses that are used in this possibility
            $size_of_course+=$sizes[$nr];
        }
        else{
            //remove zeros
            unset($previous[$nr]);
        }


    }
    //the size of the course has to be lower or same as the size limit
    //now without the zeros, count($previous) gives you the amount of courses taken in this possibility
    if ($size_of_course<=$limit&&count($previous)>=$minimum){
       //if it fits, save this possibility in the $possible array
       $possible[]=$previous;

    }


    return;
}

希望我能帮到你。

要确定这一点：“如果有计算机(Lec)，它只会在计算机(Lab)也存在的情况下才会接受它作为可能的组合”：将$possible[]=$previous;替换为：

           //further conditions are placed here



           //IMPORTANT: the name of the courses down here (in_array('Computer(lec)') have to be EXACTLY the same as in the array $courses.
           //e.g. if in $courses array the name is 'computer(lec)' and down here it's 'Computer(lec)' (uppercase) or 'computer (lec)' (space) it DOES NOT WORK!

           //if Computer(lec) is present...
           if(in_array('Computer(lec)',$previous)){
               //Computer(lab) has to be present too
               if(in_array('Computer(lab)',$previous)){
                   $possible[]=$previous;
               }
               else {
                   //if its not present dont save
                   //do nothing
               }
           }
           else{
           //if computer(lec) is not present, no problem, just save
               $possible[]=$previous;
           }

所以最终的代码应该是

$courses=array('English','Math','Computer(lec)','Computer(lab)');
$sizes = array('1','1','2','2');
//maximum 6 hours
$limit=9;
//minimum 3 courses
$minimum=0;

$possible= array();
function get_comb($previous, $depth){

    global $courses;
    $count=count($courses);
    global $possible;
    global $sizes;
    global $limit;
    global $minimum;

    //the end of the $courses array is reached
    if ($depth>$count){
        $size_of_course=0;
        foreach($previous as $nr=>$course){
            if($course !== 0){
                //the index of $previous is the same as in $courses and $sizes, so
                //$previous[1],$courses[1],$sizes[1] is logicaly referring to the same course
                //add up all sizes of the courses that are used in this possibility
                $size_of_course+=$sizes[$nr];
            }
            else{
                //remove zeros
                unset($previous[$nr]);
            }


        }
        //the size of the course has to be lower or same as the size limit
        //now without the zeros, count($previous) gives you the amount of courses taken in this possibility




        if ($size_of_course<=$limit&&count($previous)>=$minimum){
           //further conditions are placed here



           //IMPORTANT: the name of the courses down here (in_array('Computer(lec)') have to be EXACTLY the same as in the array $courses.
           //e.g. if in $courses array the name is 'computer(lec)' and down here it's 'Computer(lec)' (uppercase) or 'computer (lec)' (space) it DOES NOT WORK!

           //if Computer(lec) is present...
           if(in_array('Computer(lec)',$previous)){
               //Computer(lab) has to be present too
               if(in_array('Computer(lab)',$previous)){
                   $possible[]=$previous;
               }
               else {
                   //if its not present dont save
                   //do nothing
               }
           }
           else{
           //if computer(lec) is not present, no problem, just save
               $possible[]=$previous;
           }


        }


        return;
    }


    //either you have this course...
    get_comb(array_merge($previous,array($courses[$depth-1])),$depth+1);
    //or you dont..
    get_comb(array_merge($previous,array(0)),$depth+1);


}
get_comb(array(),1);


//output
echo '<pre>';
var_dump($possible);

Answer 2

尝试如下所示的递归

<?php
$aviCourses = array(
    "English"=>1,
    "Math"=>3,
    "Algebra"=>3,
    "History"=>1,
    "Computer(lec)"=>2,
    "Computer(lab)"=>1
);
$foundCombinations = array();
function fillBucket($courses , $remainder ) {
    global $aviCourses,$foundCombinations;
    if($remainder < 0) return; //overfill
    //else first of all put this compination in the list
    $foundCombinations[] = $courses;
    //for every avalable cource which is not in $courses yet
    foreach(array_diff(array_keys($aviCourses),$courses) as $candidate) {
        //call fill bucket recursive
        fillBucket(
            //append the candidate to the courses
            array_merge($courses,array($candidate)),
            //decrement the hours counter
            $remainder-$aviCourses[$candidate]
        );
    }
}
fillBucket(array(),9);
//filter out the duplicates with different order of lectures
array_walk($foundCombinations, sort);
array_walk($foundCombinations, function(&$v){$v = implode($v,',');});
$foundCombinations = array_unique($foundCombinations);
sort($foundCombinations);
array_walk($foundCombinations, function(&$v){$v = explode(',',$v);});
//end filter out
print_R($foundCombinations);