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
permutations
Moderator: General Moderators
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
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.
- Kieran Huggins
- DevNet Master
- Posts: 3635
- Joined: Wed Dec 06, 2006 4:14 pm
- Location: Toronto, Canada
- Contact:
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
- stereofrog
- Forum Contributor
- Posts: 386
- Joined: Mon Dec 04, 2006 6:10 am
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"));