> I already had a solution... but I felt it was bruit-force. I was wanting
> a more optimized solution/algorithm... and was having a brain-fart.
> Sorry I didn't indicate that.
Dan:
The problem of permutations cannot possibly have a better than O(N!) solution -
you do need to spit out N! worth of answers.
So to optimize in your situation, there are two approaches:
* first of all, try at all costs to avoid the N! of answers - see if the
caller can be optimized to use a better algorithm so it can solve its problem
some other way
* if there is no way around the N! permutations, then do your brute force in a
C module
I also noticed that your algorith does not solve the problem - this is the test
case that fails:
<?
function combos($data) {
$result[] = implode(' ', $data);
foreach ($data as $item) {
$match = "$item ";
foreach ($data as $other_item) {
$match .= $other_item != $item ? "$other_item " : '';
}
$result[] = trim($match);
}
return $result;
}
$t = array("1","2","3","4");
$res = combos($t);
for ($i = 0; $i < count($res); $i++)
{
print($res[$i]."\n");
}
?>
The correct algorithm will produce 24 permutations, while the one you posted
gives only 5, two of them identical.
As was already noted, a recursive solution is perhaps the easiest way to solve
the problem. It would take me about 30 minutes I do not have today to code/debug
one, so I'll just give you a general idea - make a function that can give you
all permitations but accepts a "pinned" mask - an array of flags indicating
which elements are not to be permuted. The function pins each unpinned element,
calls itself once with the new pinned mask for each possible value of that
element (out of the unpinned set), then unpins it and goes to the next one.
I do really hope, though that you can avoid doing O(N!) algorithm. Post the
original problem that created the need for the permutations - maybe somebody can
think of something better.
--
Sasha Pachev
AskSasha Linux Consulting
http://www.asksasha.com
.===================================.
| This has been a P.L.U.G. mailing. |
| Don't Fear the Penguin. |
| IRC: #utah at irc.freenode.net |
`==================================='
