All possible combinations algorithm

Sasha Pachev sasha at surveyz.com
Wed Jun 15 15:03:01 MDT 2005


 > 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




More information about the PLUG mailing list