php - How can I modify a traditional cartesian product to reduce my memory overhead? -

for problem you're selecting 24 items pool of maybe 5-10,000 items. in other words we're generating configurations.

the number 24 comes item categories, each item associated particular installation location, item location 1 cannot installed in location 10, have arranged associative array organize data in groups. each item looks like:

$items[9][] = array("id" => "0", "2" => 2, "13" => 20); 

where first parameter ( $item[9] ) tells location allowed in. if want it's ok think of idea cannot install tire in spot exhaust pipe.

the items stored in mysql database. user can specify restrictions on solution, example, attribute 2 must have final value of 25 or more. can have multiple competing restrictions. queries retrieve items have value attributes under consideration (unspecified attributes stored don't calculations them). php script prunes out redundant choices (for example: if item 1 has attribute value of 3 , item 2 has attribute value of 5, in absence of restriction never choose item 1).

after processing has occurred associative array looks like:

$items[10][] = array("id" => "3", "2" => 2, "13" => 100); $items[10][] = array("id" => "4", "2" => 3, "13" => 50); $items[9][] = array("id" => "0", "2" => 2, "13" => 20); $items[9][] = array("id" => "1", "2" => -1, "13" => 50); 

i have posted full example data set @ this pastebin link. there reason believe can more restrictive on accept data set @ restriction of 2 elements per option there's problem.

in array() value, id reference index of item in array, , other values attribute id , value pairs. $items[10][] = array("id" => "3", "2" => 2, "13" => 100); means in location 10 there item id 3 value of 2 in attribute 2 , value of 100 in attribute 13. if helps think of item being identified pair eg (10,0) item 0 in location 10.

i know i'm not being specific, there 61 attributes , don't think changes structure of problem represent. if want, can think of attribute 2 weight , attribute 13 cost. problem user wants solved might generate configuration weight 25 , cost minimized.

back of envelope math says rough estimate, if there 2 choices per location, 2^24 choices x size of record. assuming 32 bit integer encoded represent single record somehow, we're looking @ 16,777,216 * 4 = 67,108,864 bytes of memory (utterly ignoring data structure overhead) , there no reason believe either of these assumptions going valid, though algorithm upper memory bound in realm of 67 megs acceptable memory size.

there's no particular reason stick representation, used associative arrays since have variable number of attributes use , figured allow me avoid large, sparse array. above "2"=>2 means filtered attribute id #2 has value of 2 , attribute 13's value 100. i'm happy change data structure more compact.

one thought had have evaluation criteria can use discard of intermediate configurations. example, can compute 75 * "value of "2"" + 10 * "value of "13" provide relative weighting of solutions. in other words, if there no other restrictions on problem, each value improvement 1 of attribute 2 costs 75 , each value improvement of attribute 13 costs 10. continuing idea of car part, think of buying stock part , having machinist modify our specifications.

one problem see discarding configurations weighting function not take account restrictions such "the final result must have value of "2" @ 25". it's fine if have full 24 element configuration, can run through loop of restrictions, discard solutions don't match , rank remaining solutions function, i'm not sure there's valid line of thought allows me throw away solutions earlier.

does have suggestions on how move forward? although language agnostic solution fine, implementing in php if there's relevant language feature might useful.

i solved issue memory performing depth first cartesian product. can weigh solutions 1 @ time , retain if choose or output them doing here in code snippet.

the main inspiration solution came the concise answer on question. here code seems finding php depth first cartesian product algorithm less trivial.

function dfcartesian ( $input, $current, $index ) {     // sample use: $emptyarray = array();     //             dfcartesian( $items, $emptyarray, 0 )     if ( $index == count( $input ) ) {         // if have iterated on entire space , @ bottom         // whatever relevant problem , return.         //         // if improve solution suppose i'd pass in         // optional function name pass data if desired.         var_dump( $current );         echo '<br><br>';         return;     }      // i'm using non-sequential numerical indicies in associative array     // want skip empty numerical index without aborting.     //     // if you're using different think change     // needs attention change $index + 1 different type of     // key incrementer.  sort of issue tackled @     // https://stackoverflow.com/q/2414141/759749     if ( isset ( $input[$index] ) ) {         foreach ( $input[$index] $element ) {             $current[] = $element;             // despite concern recursive function overhead,             // handled 24 levels quite smoothly.             dfcartesian( $input, $current, ( $index + 1 ) );             array_pop( $current );         }     } else {         // move next index if there gap         dfcartesian( $input, $current, ( $index + 1 ) );     } }    

i hope of use else tackling same problem.