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),
)
a function for building an array of all possible combos?
Moderator: General Moderators
- 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?
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.
Although I don't know why the hell you'd want an array like that.
Re: a function for building an array of all possible combos?
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;
}
- 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?
Shorter and much more efficient:
I did a quick benchmark with 11 items, iterating each function 10 times, and got:
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.
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));
Code: Select all
1st imp: 5.3936619758606
2nd imp: 0.35965991020203