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



More information about the PLUG mailing list