Programming Challenge...Get array of variations
Ok, here is a fun one I had to do today. I got it, but kinda messy, tomorrow I'm working on streamlining it.
Say you have these "options" for shirts (the number are the database ID's)
Color[2]: red[11], blue[12], green[13]
Size[3]: small[21], med[22], large[23]
Sleeves[4]: Long[31], Small[32]
The data comes in in the following:
$aryData = array(2=>array(11,12,13),
3=>array(21,22,23),
4=>array(31,32));Now I need an array of all possible variations with the values from the above array to be in this format:
$aryVariations = array(array(11,21,31), // red, small, long
array(11,21,32), // red, small, short
array(11,22,31), // red, med, long
array(11,22,32), // red, med, short
array(11,23,31), // red, large, long
array(11,23,32), // red, large, short
array(12,21,31), // blue, small, long
......[edit] forgot to mention, there is $aryVarIndex that lists the order of the attribute types $aryVarIndex = array(2,3,4); so that the names can be matched up when listing out the variations later.[/edit]
Like I said, I do have it, but the way I got it required me to do a few intermediate arrays. The project I need it on will always only have less than 50 variations.
So if you are like me, and love a challenge, let me know what you can come up with, or at the very least, what the heck the real "name" of this procedure is so I can look it up for a more optimized way.
Thanks.
-Greg
teammatt3 posted this at 03:34 — 2nd July 2009.
He has: 2,102 posts
Joined: Sep 2003
That's a Cartesian product. You might be able to solve the problem with SQL.
{11,12,13} * {21,22,23} * {31,32} = {(11,21,31), (11, 21, 32), (11, 22, 31), (11, 22, 32)} etc. I had to do this by hand for my discrete math class. It look forever.
What does your DB schema look like?
And, before Abhishek Reddy has a chance to point it out, Python 2.6+ has a method available to do it for you
Abhishek Reddy posted this at 19:05 — 2nd July 2009.
He has: 3,348 posts
Joined: Jul 2001
I would never! I much prefer:
(ns example (:use [clojure.contrib.combinatorics]))(doseq [element (apply cartesian-product some-seqs)](println element))
Here's a first pass at a more complete PHP version:
<?php
function cartesian_product_appending ($array1, $array2) {
$result = array();
foreach ($array1 as $a) {
foreach ($array2 as $b) {
$r = $a;
if (is_array($a))
array_push($r, $b);
else
$r = array($a, $b);
array_push($result, $r);
}
}
return $result;
}
function cartesian_product_of_arrays ($arrays) {
$result = array_shift($arrays);
foreach ($arrays as $array) {
$result = cartesian_product_appending($result, $array);
}
return $result;
}
$aryData = array(2=>array(11,12,13),
3=>array(21,22,23),
4=>array(31,32));
print_r(cartesian_product_of_arrays($aryData));
?>
Greg K posted this at 15:18 — 2nd July 2009.
He has: 2,145 posts
Joined: Nov 2003
THANK YOU! I knew there had to be a name for it. now I can google it better! (or bing it better...)
I'm about to dive into cleaning up the mess of code I have to make it, will post the final version here (or a link to a function that will do the same for me)
For the gist of the DB:
tblAttribute
AttributeID
AttributeName
tblAttributeValue
AttributeValueID
AttriuteID - FK back to tblAttribute
AttributeValue
tblProductAttVal
ProductAttValID
AttributeValueID - FK back to tblAttributeValue
Available - Basically if set, this value is available on this product
note there are other values in use, and there are needs that require it broken down this way out of the scope of my needs here, but this is the gist of the table/fields that affect my challenge.
-Greg
Greg K posted this at 17:42 — 2nd July 2009.
He has: 2,145 posts
Joined: Nov 2003
Ok, now that I know what to look for, there is an example function right in the comments on php.net to do it. I'll have to adapt it a bit, but should work.
-Greg
Greg K posted this at 21:00 — 2nd July 2009.
He has: 2,145 posts
Joined: Nov 2003
Here is what I finally came up with that, trust me, is cleaner that than last nights code big time.
// $aryMatrix = contains the data, and at this point already know there
// there is at least one combination and less than 50
$intMaxVar = 1; // Will hold the maximum # of variations
foreach($aryMatrix as $aryMatrixData) $intMaxVar *= count($aryMatrixData);
$aryVariations = array_fill(0,$intMaxVar,array(array_fill(0,count($aryMatrix),0));
$intSecOffset = $intMaxVar;
for($iAtt=0; $iAtt<count($aryData); $iAtt++) {
$intAttValCount = count($aryMatrix[$iAtt]['ValIDs']);
$intSets = $intSecOffset / $intAttValCount;
for ($iAttVal=0; $iAttVal<$intAttValCount; $iAttVal++) {
for ($iOffset=0; $iOffset<$intMaxVar; $iOffset+=$intSecOffset) {
for ($iSetPos=0; $iSetPos<$intSets; $iSetPos++) {
$aryVariations[$iAttVal*$intSets+$iOffset+$iSetPos][$iAtt] = $aryMatrix[$iAtt]['ValIDs'][$iAttVal];
} } }
$intSecOffset /= $intAttValCount;
}
Yeah, it loops through total combinations * # attributes, but I know I have a set # for both of these.
Now, the next step I may tackle, here is how the data is originally, (which gets converted to the aryMatrix that I mentioned in my first post):
$aryData = array( ATT_ID => array( 'Name'=> ATT_NAME, 'Values'=> array(VAL_ID => VAL_NAME)),ATT_ID => array( 'Name'=> ATT_NAME, 'Values'=> array(VAL_ID => VAL_NAME)),
(etc)
I think I'm good where I am at. Abhishek, I'll try out your code tomorrow, and do some resource checking/timing tests to see which route to take. I am very grateful for your post, as I just wet back through my entire history in firefox for today, and i cannot find the solution on the PHP documentation site! weird!
-Greg
Want to join the discussion? Create an account or log in if you already have one. Joining is fast, free and painless! We’ll even whisk you back here when you’ve finished.