The way I would tackle this is in several steps (and maybe combine them later?) Here goes - in pseudo code/point form
1. Find max 2. Find all array elements who's number in less than max 2a. create a temp array that holds these indexes 3. Do the ol' nPr (or is it nCr?) thingo on the temp array, then using that to refer the the actual array. HTH (and it's not too confusing) Martin -----Original Message----- From: Michael Benbow [mailto:[EMAIL PROTECTED]] Sent: Wednesday, July 03, 2002 4:07 PM To: [EMAIL PROTECTED] Subject: [PHP] Find all combinations of numbers Hi, I searched through the archives and found the following snippit of code from Tim Converse from late 2000. This is great, but does anyone know how I can adapt this so I can return all values from a multidimensional array? I have an id number which corresponds to a record which I need to revisit once I get all possible combinations (not just the max which below gives us) and I do not want to lose the link between the id and the number. For instance: $number[0]['id']=5; $number[0]['number']=500; $number[1]['id']=7; $number[1]['number']=500; $number[2]['id']=23; $number[2]['number']=750; $number[3]['id']=3; $number[3]['number']=1500; $max is assigned the value 1350 in this example, so we know id 3 will be eliminated off the bat. What I need to get back are the combinations of ID's where their corresponding number are less than or equal to value $max. So in this instance I might get something like; 5 7 23 5&7 5&23 7&23 I have spent about 40 hours in the last three days on this problem alone and I can honestly say I am stuck. You guys are my last hope. Please help a desperate man! Thanks, Michael. -~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~- Tim's code: function maximum_subset_sum ($max, $candidate_array) { $working_array = array(); while ($next = each($candidate_array)) { $candidate = $next['value']; $sums_to_date = array_keys($working_array); while ($marked_sum = each($sums_to_date)) { $known_sum = $marked_sum['value']; $possibly_new = $known_sum + $candidate; if(($possibly_new <= $max) && !IsSet($working_array[$possibly_new])){ $working_array[$possibly_new] = $candidate; } } if(($candidate <= $max) && !IsSet($working_array[$candidate])){ $working_array[$candidate] = $candidate; } } $max_sum = max(array_keys($working_array)); $return_array = array($working_array[$max_sum]); while ($max_sum != $working_array[$max_sum]) { $max_sum = $max_sum - $working_array[$max_sum]; array_push($return_array, $working_array[$max_sum]); } return($return_array); } // example use $best_sum = maximum_subset_sum(40, array(39,23,19,14,9,5,3,2,1)); print("Largest sum is " . array_pop($best_sum)); while ($value = array_pop($best_sum)) { print(" + $value"); } // will print "Best sum is 23 + 14 + 3" -~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~- -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
