permutations

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
Illusionist
Forum Regular
Posts: 903
Joined: Mon Jan 12, 2004 9:32 pm

permutations

Post by Illusionist »

i'm at an absolute lost at how the best way to do this would be.
I'm looking for a way to give all possible combinations of word any length, given an initial set of characters

so say i was using abc i want

a
b
c
ab
ac
bc
abc
....

the order does not matter (abc == bac) because they will all be permutated.

i was thinking of passing the original set through the permatations, and getting the first originalLength - 1 returns and running the permutations on those, and keep going, but i'm not sure if that would work and/or be the most effecient.

if anyone has seen something like this, or heard of it, please let me know.

Thanks
User avatar
pickle
Briney Mod
Posts: 6445
Joined: Mon Jan 19, 2004 6:11 pm
Location: 53.01N x 112.48W
Contact:

Post by pickle »

Well, I think it would be easiest if you treated the string like an array, then loop through the array. Recursion would be helpful here I think.

The only big stumbling block I can think of would be how to prevent 'bac' from being recorded if 'abc' already is.

Not sure if this will help, but here's a link: viewtopic.php?t=39395
Real programmers don't comment their code. If it was hard to write, it should be hard to understand.
User avatar
Kieran Huggins
DevNet Master
Posts: 3635
Joined: Wed Dec 06, 2006 4:14 pm
Location: Toronto, Canada
Contact:

Post by Kieran Huggins »

Could be optimized I'm sure, but this works:

Code: Select all

function perm($string){

	$output = array();

	$a = str_split($string);
	sort($a);
	$output[]=implode('',$a);

	for($i=0;$i<strlen($string);$i++){
		$arr = perm(substr_replace($string,'',$i,1));
		$output = array_merge($output,$arr);
	}
	
	sort($output);
	return array_values(array_diff(array_unique($output),array('')));

}
Illusionist
Forum Regular
Posts: 903
Joined: Mon Jan 12, 2004 9:32 pm

Post by Illusionist »

thank you both.
Kieran, I think i'm going to use your function, and work from it a bit.

Thanks
User avatar
stereofrog
Forum Contributor
Posts: 386
Joined: Mon Dec 04, 2006 6:10 am

Post by stereofrog »

Illusionist, strictly speaking what you're looking for is called combinations, not permutations (the difference is that combinations are unaware of the order of elements). Finding combinations (of non-repeating elements!) usually involves binary arithmetic:

Code: Select all

function combinations($s) {
	$len = strlen($s);
	$res = array();
	for($n = 1; $n < (1 << $len); $n++) {
		$tmp = '';
		for($b = 0; $b < $len; $b++)
			if(($n >> $b) & 1) $tmp .= $s[$b];
		$res[] = $tmp;
	}
	return $res;
}

print_r(combinations("abcd"));
Post Reply