Page 1 of 1

permutations

Posted: Thu Mar 15, 2007 1:11 pm
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

Posted: Thu Mar 15, 2007 1:20 pm
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

Posted: Thu Mar 15, 2007 2:08 pm
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('')));

}

Posted: Thu Mar 15, 2007 2:30 pm
by Illusionist
thank you both.
Kieran, I think i'm going to use your function, and work from it a bit.

Thanks

Posted: Fri Mar 16, 2007 6:07 am
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"));