a function for building an array of all possible combos?

Not for 'how-to' coding questions but PHP theory instead, this forum is here for those of us who wish to learn about design aspects of programming with PHP.

Moderator: General Moderators

Post Reply
phpNewb
Forum Newbie
Posts: 6
Joined: Fri Feb 03, 2006 2:07 pm

a function for building an array of all possible combos?

Post by phpNewb »

does anyone know of either an existing function, or the proper (most efficient) algorithm for taking an array of values, and converting it to an array of every possible combination of those values?

In other words, a way to convert:
array(1, 2, 3)
into:
array(
array(1),
array(1, 2),
array(1, 3),
array(1, 2, 3),
array(2),
array(2, 3),
array(3),
)
User avatar
Ambush Commander
DevNet Master
Posts: 3698
Joined: Mon Oct 25, 2004 9:29 pm
Location: New Jersey, US

Re: a function for building an array of all possible combos?

Post by Ambush Commander »

Treat each entry in the array as a bit. Go from 0...2^(number of bits) - 1, and logical AND & each value to determine whether or not it goes in the array.

Although I don't know why the hell you'd want an array like that. :?
phpNewb
Forum Newbie
Posts: 6
Joined: Fri Feb 03, 2006 2:07 pm

Re: a function for building an array of all possible combos?

Post by phpNewb »

Here is the solution, in case anyone is interested (please share any efficiency tweaks). In answer to the question above, this was necessary for a new approach to achieving ANN (Artificial Neural Network)-type functionality with a much smaller codebase and level-of-complexity than what is currently available.

Code: Select all

 
        /**
         * Returns arrays of every possible combination of values
         *
         * Returns a multi-level array with a sub-array for every possible
         * combination of one or more values.
         *
         * @param array $values An array of scalar values
         * @return array An array for every possible combination of values
         */
        function getAllCombinations($values)
        {
            $combos = array();
            foreach ($values as $value1)
            {
                // begin the set with the current value
                $set = array($value1);
                // add each value to the set one at a time
                foreach ($values as $value2)
                {
                    $set[] = $value2;
                    sort($set);
                    $set = array_unique($set);
                    if (!in_array($set, $combos)) $combos[] = $set;
                }
                // repeat every existing array without the current value
                foreach ($combos as $combo)
                {
                    $key = array_search($value1, $combo);
                    if (count($combo) > 1 && $key !== FALSE)
                    {
                        unset($combo[$key]);
                        if (!in_array($combo, $combos)) $combos[] = $combo;
                    }
                }
            }
            return $combos;
        }
 
User avatar
Ambush Commander
DevNet Master
Posts: 3698
Joined: Mon Oct 25, 2004 9:29 pm
Location: New Jersey, US

Re: a function for building an array of all possible combos?

Post by Ambush Commander »

Shorter and much more efficient:

Code: Select all

<?php
 
$values = array('a', 'b', 'c');
 
function getAllCombinations($values) {
    $c = count($values);
    $max = 1 << $c;
    $ret = array();
    // Set starting value for $i = 0 if you want array() as part of the solutions
    for ($i = 1; $i < $max; $i++) {
        $val = array();
        for ($j = 0; $j < $c; $j++) {
            if ($i & (1 << $j)) {
                $val[] = $values[$j];
            }
        }
        $ret[] = $val;
    }
    return $ret;
}
 
print_r(getAllCombinations($values));
 
I did a quick benchmark with 11 items, iterating each function 10 times, and got:

Code: Select all

1st imp: 5.3936619758606
2nd imp: 0.35965991020203
It is limited, however, by how big your integer is (32-bit system means wesupport a max of 32 items (actually, a little less because of signing?)_). Also, PHP doesn't seem to be the best language for simulating neural nets.
Post Reply