On Wednesday 15 June 2005 03:03 pm, Sasha Pachev wrote:
> 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.
A half hour? Sasha, you're loosing your touch! ;)
Your suggested 'pinning' solution seems more complicated than necessary.
>
> 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.
As others mentioned, the size of the solution is O(N!), thus the algorithm can
be no better.
Here's a quicky PHP version:
(note: it does no input validation--non or empty array will probably break it)
function &combinations($items) {
if (count($items) == 1) {
return $items;
}
$ret = array();
$items_as_keys = array_flip($items);
foreach ($items as $i) {
$tmp = $items_as_keys;
unset($tmp[$i]);
$subs =& combinations(array_keys($tmp));
foreach ($subs as $s) {
$ret[] = $i . ' ' . $s;
}
}
return $ret;
}
print_r(combinations(array('a', 'b', 'c')));
--
Respectfully,
Nicholas Leippe
Sales Team Automation, LLC
1335 West 1650 North, Suite C
Springville, UT 84663 +1 801.853.4090
http://www.salesteamautomation.com
.===================================.
| This has been a P.L.U.G. mailing. |
| Don't Fear the Penguin. |
| IRC: #utah at irc.freenode.net |
`==================================='
