<?php
//    /** 
//      * Use the to find all values in an array that, combined, will give the desired results
//      *
//     * @author sdunn
//     */
    class sortArrayProblems
    {
        // $this->dp[$i][$j] is going to store true if $summedTotal $j is 
        // possible with array elements from 0 to $i. 
        private $dp=null; 
        
        // This variable will be an array of the arrays that will make the specified 
        // results combination
        public $allExactCombinations=null;
        
//        // Array Order By waste
//        public $arrayOrderByTotalWaste=null;
        
        // Error string to fill for any problems
        public $errorString="";
        
        function __construct() {
            $this->dp=array();
            $this->allExactCombinations=array();
//            $this->arrayOrderByTotalWaste=array();
        }
        
        // Function to add the waste amount to the decondary arrays of the main array
        private function addUpWasteAmount(){
            // Determine if the array exists and has a count
            if ($this->allExactCombinations!=NULL && count($this->allExactCombinations) > 0){
                // Loop through the main array
                for ($loopNumber1=0; $loopNumber1<count($this->allExactCombinations); $loopNumber1++){
                    // create a number to hold the waste amount
                    $totalWaste = 0;
                    
                    // Now determine if the inner array is an array and has count
                    if ($this->allExactCombinations[$loopNumber1]!=NULL && count($this->allExactCombinations[$loopNumber1]) > 0){
                        // Loop through the second array
                        for ($loopNumber2=0; $loopNumber2<count($this->allExactCombinations[$loopNumber1]); $loopNumber2++){
                            // Increase the waste amount with the third and final array
                            $totalWaste = $totalWaste + $this->allExactCombinations[$loopNumber1][$loopNumber2]["Waste"];
                        }
                    }
                    
                    // Add the total waste to the secondary array
                    array_push ($this->allExactCombinations[$loopNumber1], array('ArrayLocation' =>  $loopNumber1, 'TotalWaste' => $totalWaste));

//                    // Create the Array to help me keep order
//                    array_push ($this->arrayOrderByTotalWaste, array('ArrayLocation' =>  $loopNumber1, 'TotalWaste' => $totalWaste));
                }
            }
            
//var_dump($this->arrayOrderByTotalWaste);
//print "<BR>\n<BR>\n";
//echo '<script>alert("Here");</script>';
//for ($loopNumber1=0; $loopNumber1<count($this->allExactCombinations); $loopNumber1++){
//    print $this->allExactCombinations[$loopNumber1][count($this->allExactCombinations[$loopNumber1])-1]["ArrayLocation"]. ':' . $this->allExactCombinations[$loopNumber1][count($this->allExactCombinations[$loopNumber1])-1]["TotalWaste"] . '<BR>';
//    print ':' . $this->allExactCombinations[$loopNumber1][count($this->allExactCombinations[$loopNumber1])-1] . '<BR>';
//}
//print "<BR>\n<BR>\n";

            // Sort ascending on the wast amount so we can have it ordered nicely
            usort($this->allExactCombinations, function ($a,$b) 
            {
                // Determine if a is larger or equal
                if($a[count($a)-1]["TotalWaste"] - $b[count($b)-1]["TotalWaste"] >= 0){
                    // Return higher response
                    return 1;
                }

                // Return lower response
                return -1;
            });

////asort($this->arrayOrderByTotalWaste);
//for ($loopNumber1=0; $loopNumber1<count($this->allExactCombinations); $loopNumber1++){
//    for ($loopNumber2=0; $loopNumber2<count($this->allExactCombinations[$loopNumber2]);$loopNumber2++)
//        print $this->allExactCombinations[$loopNumber1][count($this->allExactCombinations[$loopNumber1])-1]["ArrayLocation"]. ':' . $this->allExactCombinations[$loopNumber1][count($this->allExactCombinations[$loopNumber1])-1]["TotalWaste"] . '<BR>';
////    print ':' . $this->allExactCombinations[$loopNumber1][count($this->allExactCombinations[$loopNumber1])-1] . '<BR>';
//}
//print "<BR>\n<BR>\n";

//var_dump($this->arrayOrderByTotalWaste);
//echo '<script>alert("There");</script>';
//print "<BR>\n<BR>\n  ErrorString:" ;
//var_dump($this->allExactCombinations);

        }
        
        // A recursive function to print all subsets with the 
        // help of $this->dp[][]. Vector $p[] stores current subset. 
        private function printSubsetsRec($stockArray, $i, $summedTotal, &$p) 
        { 
            // If we reached end and $summedTotal is non-zero. We print $p[] only if 
            // $stockArray[0][1] is equal to sun OR $this->dp[0][$summedTotal] is true. 
            if ($i == 0 && $summedTotal != 0 && $this->dp[0][$summedTotal]) 
            { 
                // Add the stock to the passed in array
                array_push($p, $stockArray[$i]); 

                // Add the combination to the combination array
                array_push($this->allExactCombinations, $p);
                
                // Clear the passed in array
                unset($p); 
            } 

            // If $summedTotal becomes 0 
            if ($i == 0 && $summedTotal == 0) 
            { 

                // Add the combination to the combination array
                array_push($this->allExactCombinations, $p);
                
                // Clear the passed in array
                unset($p); 
            } 

            // If given $summedTotal can be achieved after ignoring current element. 
            if ($this->dp[$i-1][$summedTotal]) 
            { 
                // Create a new vector to store path 
                $b=array();
                $b=$p; 
                
                // build another array
                $this->printSubsetsRec($stockArray, $i-1, $summedTotal, $b); 
            } 

            // If given $summedTotal can be achieved after considering current element. 
            if ($summedTotal >= $stockArray[$i]["MaxBlanks"] && $this->dp[$i-1][$summedTotal-$stockArray[$i]["MaxBlanks"]]) 
            { 
                // Increase the wast amount by the waste of this blank being added
                array_push($p, $stockArray[$i]); 
                
                // build another array
                $this->printSubsetsRec($stockArray, $i-1, $summedTotal-$stockArray[$i]["MaxBlanks"], $p); 
            }
        } 

        // Prints all subsets of $stockArray[0..$n-1] with $summedTotal 0. 
        function printAllSubsets($stockArray, $summedTotal) 
        { 
            // Get the amount in the array
            $arrayAmount = count($stockArray);
            
            // Determine if there is nothing in the array or the number of minimum amount is zero or less
            if ($arrayAmount == 0 || $summedTotal < 0) {
                // Leave the function because cannot do calculations on those amounts
                return; 
            }

            // create an array of empty boolean elements to the size of the amount we are trying to fit into
            $dpGenericElementArray = Array();
            for ($i=0; $i<$summedTotal+1; ++$i) 
            { 
                // Adds a boolean flag for the element initialized to all false
                array_push($dpGenericElementArray,false);   
            } 
            
            // Sum 0 can always be achieved with 0 elements 
            for ($i=0; $i<$arrayAmount; ++$i) 
            {
                // Add the first element as the generic array (hopefully deep copy)
                array_push($this->dp, $dpGenericElementArray);
                
                // Set the first element of the inner array to zero
                $this->dp[$i][0] = true;   
            } 

            // Sum $stockArray[0] can be achieved with single element 
            if ($stockArray[0]["MaxBlanks"] <= $summedTotal) {
                // Set the position of the zero array to be true since it fits
                $this->dp[0][$stockArray[0]["MaxBlanks"]] = true; 
            }

            // Fill rest of the entries in $this->dp[][] 
            for ($i = 1; $i < $arrayAmount; ++$i) {
                // Add the inner array to the outer array (hopefully deep copy)
                array_push($this->dp, $dpGenericElementArray);

                // Loop through this new inner array
                for ($j = 0; $j < $summedTotal + 1; ++$j) {
                    // Do some boolean math to check the element 
                    $this->dp[$i][$j] = ($stockArray[$i]["MaxBlanks"] <= $j) ? ($this->dp[$i-1][$j] || 
                                               $this->dp[$i-1][$j-$stockArray[$i]["MaxBlanks"]]) 
                                             : $this->dp[$i - 1][$j]; 
                }
            }
            
            // Determine if this one works or not
            if ($this->dp[$arrayAmount-1][$summedTotal] == false) 
            { 
                // Create a string that can be used to let people know we cannot 
                // fill the order with blanks that cannot fill a full order
                $errorString .= 'There are not enough blanks that cannot handle the ' .
                                'entire order that can be combined to fill the order.';
                
                return; 
            } 

            // Now recursively traverse $this->dp[][] to find all 
            // paths from $this->dp[$arrayAmount-1][$summedTotal] 
            $p = array(); 
            $this->printSubsetsRec($stockArray, $arrayAmount-1, $summedTotal, $p); 
            
            // Add the waste amount to the main array's secondary arrays and sort 
            // ascending on total waste
            $this->addUpWasteAmount();
        } 
    } 
?>
