Combinatratics

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Combinatratics

Post 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.
Last edited by Weirdan on Fri Jul 23, 2010 2:46 pm, edited 1 time in total.
Reason: fixed syntax tags. [php] is b0rken, use [syntax=php]
Bruno De Barros
Forum Commoner
Posts: 82
Joined: Mon May 12, 2008 8:41 am
Location: Ireland

Re: Combinatratics

Post by Bruno De Barros »

The code looks all messed up, is there any chance you can fix it?
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

Re: Combinatratics

Post 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;
    }
}
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Combinatratics

Post by josh »

Can you help me understand the current() function? Why does it use the modulus?
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

Re: Combinatratics

Post 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
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Combinatratics

Post 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.
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: Combinatratics

Post 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.
There are 10 types of people in this world, those who understand binary and those who don't
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: Combinatratics

Post 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.
Last edited by VladSun on Mon Jul 26, 2010 2:22 pm, edited 1 time in total.
There are 10 types of people in this world, those who understand binary and those who don't
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

Re: Combinatratics

Post 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.
User avatar
AbraCadaver
DevNet Master
Posts: 2572
Joined: Mon Feb 24, 2003 10:12 am
Location: The Republic of Texas
Contact:

Re: Combinatratics

Post by AbraCadaver »

Holy crap! Math nerds... :wink:
mysql_function(): WARNING: This extension is deprecated as of PHP 5.5.0, and will be removed in the future. Instead, the MySQLi or PDO_MySQLextension should be used. See also MySQL: choosing an API guide and related FAQ for more information.
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: Combinatratics

Post 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 ;)
There are 10 types of people in this world, those who understand binary and those who don't
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Combinatratics

Post 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.
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

Re: Combinatratics

Post by Weirdan »

What's with that red row of 1s?
User avatar
superdezign
DevNet Master
Posts: 4135
Joined: Sat Jan 20, 2007 11:06 pm

Re: Combinatratics

Post by superdezign »

So, process of elimination would be too slow? :p
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Combinatratics

Post 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?
Post Reply