# All possible combinations algorithm

Nicholas Leippe nick at byu.edu
Thu Jun 16 12:24:45 MDT 2005

```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

```