Obtenir toutes les combinaisons d'un tableau PHP

Question

J'ai juste besoin de votre aide. Je construis un système utilisant PHP sur le conseil académique. Fondamentalement, j'ai besoin d'un algorithme sur la façon d'implémenter la fonction principale du système. L'idée principale est qu'il y a une liste de cours dans un tableau et que j'ai besoin de toutes les combinaisons possibles de cette liste. Chaque cours aurait une unité/nombre qui spécifie sa taille. L'algo devrait faire des combinaisons de base sur une certaine taille.

Par exemple.

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

Taille maximum = 9.

Ainsi, le algo devrait obtenir toutes les combinaisons sans dépasser la limite de taille.

donc le résultat pourrait être comme ça.

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

Quelque chose comme ça. Merci. J'ai juste besoin de tes conseils.

Answer 1

essayez ceci:

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

dans le précédent, les cours variables additionnent alors que la fonction ne récursivité. Explication: d'abord, je calcule toutes les combinaisons possibles. Pour ce faire, je pensais que des cours comme machines à sous:

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

cela se fait avec cette partie de la fonction. Il est une fonction récursive, de sorte qu'il appelle lui-même dans la fonction:

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

supposant ceci:

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

les appels de fonction récursive se ressembler à ceci (0 signifie, vous ne prennent pas ce cours): http://img43.imageshack.us/img43/5688/flowdiagram.png

après, si elles correspondent aux exigences que je sauvegarde la possibilité de $ possible: parce que la profondeur = 3 et count = 2, la profondeur de $> $ count donc cette partie du code entre en jeu:

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

J'espère pouvoir vous aider.

--------------------------------------------- modifier --------------------------------------

pour archiver ceci: 's'il y a ordinateur (LEC), il est également présent 'n'accepterait comme une combinaison possible si l'ordinateur (de laboratoire): remplacer $possible[]=$previous; avec:

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

donc le code fini serait

$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

essayer une récursion comme celui-ci

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