Page 1 of 2

Combinatratics

Posted: Fri Jul 23, 2010 7:08 am
by josh
So I need an algorithm to generate combination of arrays. For example given the input

Code: Select all

$traits = array (
            'make' => array(1,2),
            'model' => array(1,2),
            'year' => array(1,2)
);
It should output this

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)
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:

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()) );
    }
}
The automated test for it

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] );

    }
}
PS > Feel free to use as long as you give credit where it is due.

Re: Combinatratics

Posted: Fri Jul 23, 2010 8:45 am
by Bruno De Barros
The code looks all messed up, is there any chance you can fix it?

Re: Combinatratics

Posted: Fri Jul 23, 2010 4:07 pm
by Weirdan
Adapted from http://stackoverflow.com/questions/2246 ... 07#2250207

Code: Select all

class Combiner implements Iterator
{
    protected $limit = null;
    protected $current = null;
    protected $traits = array();
    protected $names = array();

    public function setTraits($traits)
    {
        // add parameter arrays in reverse order so we can use foreach() in current()
        // could use array_reverse(), but you might want to check is_array() for each element.
        $this->names = array_keys($traits);
        foreach ($traits as $t) {
            if (!is_array($t)) {
                throw new InvalidArgumentException('$traits expected to be array of arrays');
            }
            array_unshift($this->traits, $t);
        }
        $this->current = 0;
        // there are |arr1|*|arr2|...*|arrN| elements in the result set
        $this->limit = array_product(array_map('count', $traits));
    }

    public function getCombinations()
    {
        if (is_null($this->limit)) {
            throw new BadMethodCallException('You should call setTraits() first');
        }

        $ret = array();
        foreach ($this as $combination) {
            $ret[] = $combination;
        }
        $this->limit = null; // force user to reset iterator via setTraits
        return $ret;
    }

    public  function current()
    {
        $rv = array();
        $key = $this->current;
        foreach( $this->traits as $e) {
            array_unshift( $rv, $e[$key % count($e)] );
            $key = (int)($key/count($e));
        }
        return array_combine($this->names, $rv);
    }

    public function key()
    {
        return $this->current;
    }

    public function next() {
        ++$this->current;
    }

    public function rewind()
    {
        $this->current = 0;
    }

    public function valid()
    {
        return $this->current < $this->limit;
    }
}

Re: Combinatratics

Posted: Fri Jul 23, 2010 6:20 pm
by josh
Can you help me understand the current() function? Why does it use the modulus?

Re: Combinatratics

Posted: Fri Jul 23, 2010 7:40 pm
by Weirdan
This is in fact interesting and elegant solution (not mine, sadly :twisted: ). Basically it maps ever increasing number ($this->current) to 3 other numbers, that are 'spinning' in a predefined ranges. Here how I would visualize it:

Code: Select all

  123|12|12  $this->current      year index     model index      make index
  ^  |^ |^         0             0%3=0          (0/3)%2=0        (0/3/2)%2=0
   ^ |^ |^         1             1%3=1          (1/3)%2=0        (1/3/2)%2=0
    ^|^ |^         2             2%3=2          (2/3)%2=0        (2/3/2)%2=0
  ^  | ^|^         3             3%3=0          (3/3)%2=1        (3/3/2)%2=0
   ^ | ^|^         4             4%3=1          (4/3)%2=1        (4/3/2)%2=0
    ^| ^|^         5             5%3=2          (5/3)%2=1        (5/3/2)%2=0
  ^  |^ | ^        6             6%3=0          (6/3)%2=0        (6/3/2)%2=1
   ^ |^ | ^        7             7%3=1          (7/3)%2=0        (7/3/2)%2=1
    ^|^ | ^        8             8%3=2          (8/3)%2=0        (8/3/2)%2=1
  ^  | ^| ^        9             9%3=0          (9/3)%2=1        (9/3/2)%2=1
   ^ | ^| ^       10            10%3=1         (10/3)%2=1       (10/3/2)%2=1
    ^| ^| ^       11            11%3=2         (11/3)%2=1       (11/3/2)%2=1
Left column shows $traits members and how we want their indices to be selected. Then we have the global ever increasing number. Then - formulas for each respective $trait member index.
Modulus is used to keep each index within the array bounds, and to keep it rolling over again and again. Once we used all indices from the leftmost array we 'reset' it and add one to the next index - much like if we converted number of seconds to h:m:s manually we would reset seconds to 0 and add one to minutes once we reached 60 seconds. Actually this is how you could implement digital clock (very imprecise because sleep(1) could sleep longer than 1 second):

Code: Select all

$combiner = new Combiner;
$combiner->setTraits(array('h' => range(0,23), 'm' => range(0,59), 's' =>range(0, 59)));
foreach ($combiner as $current) {
   echo $current['h'] . ':' . $current['m'] . ':' . $current['s'] . PHP_EOL;
   sleep(1);
}
If you run it for a day, it would give you all combinations of possible values for hours, minutes and seconds

Re: Combinatratics

Posted: Mon Jul 26, 2010 2:46 am
by josh
Even if you didn't write it, its brilliant! Thanks for your help I think I get this stuff now. The modulus is a tricky solution but more ideal then my "brute force" solution.

Re: Combinatratics

Posted: Mon Jul 26, 2010 5:02 am
by VladSun
I haven't read the code in depth, but the "visualization table" looks very similar to the representation and addressing of a multidimensional array into the 1D memory (RAM) space.

Re: Combinatratics

Posted: Mon Jul 26, 2010 5:19 am
by VladSun
N-D to 1-D

IX = D(n)*D_Size(n-2)*...*D_Size(1) +
+ D
(n-1)*D_Size(n-3)*...*D_Size(1) +
...
+ D
(n-m)*D_Size(n-m-1)*...*D_Size(1) +
...
+ D
(1)


1-D to N-D

D(n) = IX / D_Size(n-1) / D_Size(n-2) /.../D_Size(1)
D(n-1) = IX / D_Size(n-2) / D_Size(n-3) /.../D_Size(1)
...
D
(n-m) = IX / D_Size(n-m-1) / D_Size(n-m-2) /.../D_Size(1)
...
D
(1) = IX % D_Size(1)



PS: Probably, I will have some index mismatch mistakes in the equations above, but it will still follow the right logic.

Re: Combinatratics

Posted: Mon Jul 26, 2010 1:00 pm
by Weirdan
VladSun wrote:I haven't read the code in depth, but the "visualization table" looks very similar to the representation and addressing of a multidimensional array into the 1D memory (RAM) space.
Yes, combinations of members of several sets could be thought of as coordinates in multidimensional space where each set represents a dimension of this rectangle/cube/hypercube. If you flatten the cube into 1d then you'd be able to get all combinations by enumerating all cells and converting this 1d index into the corresponding coordinate tuples.

Re: Combinatratics

Posted: Mon Jul 26, 2010 2:10 pm
by AbraCadaver
Holy crap! Math nerds... :wink:

Re: Combinatratics

Posted: Mon Jul 26, 2010 3:22 pm
by VladSun
AbraCadaver wrote:Holy crap! Math nerds... :wink:
Nope, just developers :P We haven't used the contour integration to solve a problem ... yet ;)

Re: Combinatratics

Posted: Sat Jul 31, 2010 6:27 am
by josh
Now I have to do reverse combinations. Like you show me the full set ahead of time, and then later you show me a set but parts of it have been "folded".

Like this.
full set-
0101
0100

0111
1111

folded set-
010_
0111

output-
0101
0100

0111

From the blank parts (which can be anywhere & everywhere according to the spec), it has to go in and fill them in with only values that would make it match a row from the full set. But I can't just grab the full set because the output is supposed to be only a subset of the full set that are extrapolated from the folded set. That is confusing to write.Oh yeah and the "full set" could be a million row database table :dubious:

I've of course already got a function that would take an input row with blanks:
010_
and would return matching rows from the full set
0101
0100


I guess the solution would be like performing the above operation and then substituting or splicing in the exploded rows back into the input set.

Re: Combinatratics

Posted: Sat Jul 31, 2010 1:11 pm
by Weirdan
What's with that red row of 1s?

Re: Combinatratics

Posted: Sat Jul 31, 2010 6:13 pm
by superdezign
So, process of elimination would be too slow? :p

Re: Combinatratics

Posted: Sun Aug 01, 2010 10:51 am
by josh
Weirdan wrote:What's with that red row of 1s?
Red to indicate it should not be in the final set. Bold to show the relationship be the "folded" version and the "exploded" version in the input vs output sets.
superdezign wrote:So, process of elimination would be too slow? :p
Hmm can you elaborate? Speed is important but your idea sounds unique, for all we know its faster. But can you get in to more detail and show me like examples of how you would visualize that working?