Combinatratics
Posted: Fri Jul 23, 2010 7:08 am
So I need an algorithm to generate combination of arrays. For example given the input
It should output this
Important features were preservation of the array index, order of each key within each combination must match the input order, and it must generate combination not permutations. I didn't want partial combinations like just "make/model". Here is how I implemented it. Right now it actually goes thru first and does a permutation algorithm, and then the "removePartials" method strips the result set down to a straight combination. So its doing a lot of work it may not have to. Can anyone school me up on this and do it better or suggest a better way to wrap my head around the problem? The code works but it leaves room for improvement:
The automated test for it
PS > Feel free to use as long as you give credit where it is due.
Code: Select all
$traits = array (
'make' => array(1,2),
'model' => array(1,2),
'year' => array(1,2)
);Code: Select all
array('make'=>1,'model'=>1,'year'=>1)
array('make'=>1,'model'=>1,'year'=>2)
array('make'=>1,'model'=>2,'year'=>1)
array('make'=>1,'model'=>2,'year'=>2)
array('make'=>2,'model'=>1,'year'=>1)
array('make'=>2,'model'=>1,'year'=>2)
array('make'=>2,'model'=>2,'year'=>1)
array('make'=>2,'model'=>2,'year'=>2)
Code: Select all
<?php
class Elite_Vafimporter_Model_ArrayCombiner
{
protected $traits;
protected $allCombinations = array(array());
function setTraits( $traits )
{
$this->traits = $traits;
}
function getCombinations() {
foreach( $this->keys() as $key )
{
foreach($this->allCombinations as $previousCombination )
{
foreach( $this->traits[$key] as $value )
{
$currentCombination = $previousCombination;
$currentCombination[$key] = $value;
$this->addCombination($currentCombination);
}
}
}
$this->removePartials();
return array_values($this->allCombinations);
}
function keys()
{
return array_keys( $this->traits );
}
function valueAtIndex($key,$i)
{
return $this->traits[$key][$i];
}
function valueCount($key)
{
return count( $this->traits[$key] );
}
function addCombination($combination)
{
if( !$this->hasComination($combination) )
{
array_push($this->allCombinations,$combination);
}
}
function hasComination( $compare )
{
foreach( $this->allCombinations as $combination )
{
if( $compare === $combination )
{
return true;
}
}
return false;
}
function removePartials()
{
foreach($this->allCombinations as $key => $combination)
{
if($this->isPartial($combination))
{
unset($this->allCombinations[$key]);
}
}
}
function isPartial($combination)
{
return( count($combination) != count($this->keys()) );
}
}Code: Select all
<?php
class ArrayCombinerTest extends Elite_Vaf_TestCase
{
function test()
{
$traits = array (
'make' => array(1,2),
'model' => array(1,2),
'year' => array(1,2)
);
$combiner = new Elite_Vafimporter_Model_ArrayCombiner();
$combiner->setTraits($traits);
$r = $combiner->getCombinations();
$this->assertEquals( 8, count($r) );
$this->assertEquals( array('make'=>1,'model'=>1,'year'=>1), $r[0] );
$this->assertEquals( array('make'=>1,'model'=>1,'year'=>2), $r[1] );
$this->assertEquals( array('make'=>1,'model'=>2,'year'=>1), $r[2] );
$this->assertEquals( array('make'=>1,'model'=>2,'year'=>2), $r[3] );
$this->assertEquals( array('make'=>2,'model'=>1,'year'=>1), $r[4] );
$this->assertEquals( array('make'=>2,'model'=>1,'year'=>2), $r[5] );
$this->assertEquals( array('make'=>2,'model'=>2,'year'=>1), $r[6] );
$this->assertEquals( array('make'=>2,'model'=>2,'year'=>2), $r[7] );
}
}