Getting All combinations from an array PHP

Question

I just need your help. I'm building a system using PHP about academic advising. basically I need an algorithm on how to implement the main function of the system. The main idea is that there are a list of courses in an array and I need to get all the possible combinations from that list. Each courses would have a unit/number that specifies its size. The algo should make combinations base on a certain size.

For example.

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

Maximum Size = 9.

So the algo should get all the combinations without exceeding the size limit.

so the result could be like this.

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

Something like that. Thanks. I just need your advice.

I have done all the basic functions of the system. The list of courses is placed on a 1d array. I'm trying to get all the combinations to be placed in a 2d array. I tried using this http://stackoverflow.com/a/8880362/1010916 but cant get it to work. This basically is what i need but i cant add the size limit. thank you. — Josyl Maro, Dec 26 '12 at 13:05
And can you please help me.. I want that the combinations if there is computer(lec) it would only accept it as a possible combination if computer(lab) is also present in the combination. thank you so much — Josyl Maro, Dec 27 '12 at 08:53

Valerij · Answer 1 · 2012-12-26T14:19:14.447

try a recursion like this

<?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);

i cant make it to work. I'm just a beginner in php. and one more thing is that i need that the course array and units array are in two different variables. Because the data is coming from a database and i already made the two in two different arrays. thank you for your help. — Josyl Maro, Dec 26 '12 at 13:13
why would you tear the data apart to two arrays? you want to change the fetching routine, also i changed the code in the example to run successfully — Valerij, Dec 26 '12 at 14:18
thank you for your answer. the reason i want to use two arrays is that i dont know how to use an array like the one you used. I'll try learning this code. thanks — Josyl Maro, Dec 26 '12 at 14:52

advanced_noob · Accepted Answer · 2012-12-27T13:44:46.900

try this:

$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);

in the variable previous the courses add up while the function does recursion.

Explanation: first, i calculate all the possible combinations. To do this, I thought of the courses as slots:

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

this is done with this part of the function. It is a recursive function, so it calls itself within the function:

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);

assuming this:

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

the recursive function calls would look like this (0 means, you dont take that course): http://img43.imageshack.us/img43/5688/flowdiagram.png

after that, if they fit the requirements I save the possibility in $possible: because depth=3 and count=2, $depth>$count so this part of the code comes into play:

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;
}

hope i could help you.

---------------------------------------------edit--------------------------------------

to archieve this: 'if there is computer(lec) it would only accept it as a possible combination if computer(lab) is also present': replace $possible[]=$previous; with:

           //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;
           }

so the finished code would be

$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);

thank you for this.If possible, can you explain me the code? thank you! — Josyl Maro, Dec 26 '12 at 14:49
Thank you so much. it works great. And can you please help me.. I want that the combinations if there is computer(lec) it would only accept it as a possible combination if computer(lab) is also present in the combination. thank you so much — Josyl Maro, Dec 27 '12 at 08:16
i added that condition. look for ---edit---. but be careful, the names in the condition (in_array('Computer(lec)') have to be exactly the same as in the $courses array, character by character, otherwise it wont work. — advanced_noob, Dec 27 '12 at 13:47
okay thank you very much. I already figured it out. thanks a lot. — Josyl Maro, Dec 27 '12 at 16:23

Getting All combinations from an array PHP

2 Answers2