Combination or Permutation question!

[kanka]

Here is my problem,

I have a string like $numbers="12345 ";

i wanna find out all possible (unique) combinations of each subs.
e.g. 1 - 2 - 3 - 4 - 5 - 12 - 13 - 14 - 15 - 23 - 24 - ..... - 234 -
245 - .... - 12345
but not 11 - 22 - 21 - 32 - 321....

here is the function that i wrote not returns 13 - 14 - 15 or 24 - 25

$numbers="12345 ";
$total=strlen($ numbers);
for ($j=0; $j< $total; $j++) {
for ($k=0; $k< ($total-$j); $k++) {
$c[]=substr($number s, $k, $j+1);
}
}

[Oli Filth]

Re: Combination or Permutation question!

kanka wrote:[color=blue]
> Here is my problem,
>
> I have a string like $numbers="12345 ";
>
> i wanna find out all possible (unique) combinations of each subs.
> e.g. 1 - 2 - 3 - 4 - 5 - 12 - 13 - 14 - 15 - 23 - 24 - ..... - 234 -
> 245 - .... - 12345
> but not 11 - 22 - 21 - 32 - 321....
>
> here is the function that i wrote not returns 13 - 14 - 15 or 24 - 25
>
> $numbers="12345 ";
> $total=strlen($ numbers);
> for ($j=0; $j< $total; $j++) {
> for ($k=0; $k< ($total-$j); $k++) {
> $c[]=substr($number s, $k, $j+1);
> }
> }[/color]

This sound like you want *permutations*, not *combinations*.

You can create permutations of an array with a recursive function,
something like:

function getPermutations ($values)
{
$perms = array(null);
foreach ($values as $key => $v)
{

$temp = $values;
unset($temp[$key]);
$newPerms = getPermutations ($temp);
foreach ($newPerms as $perm)
{
$perms[] = ($v . $perm);
}
}

return $perms;
}

This is inefficient, but it works.

--
Oli

[Oli Filth]

Re: Combination or Permutation question!

Oli Filth wrote:[color=blue]
> kanka wrote:[color=green]
> > Here is my problem,
> >
> > I have a string like $numbers="12345 ";
> >
> > i wanna find out all possible (unique) combinations of each subs.
> > e.g. 1 - 2 - 3 - 4 - 5 - 12 - 13 - 14 - 15 - 23 - 24 - ..... - 234 -
> > 245 - .... - 12345
> > but not 11 - 22 - 21 - 32 - 321....
> >[/color]
>
> This sound like you want *permutations*, not *combinations*.[/color]

Oops, no, I misread. You do want combinations.

Still, it won't be hard to modify the code I posted to do combinations
instead.

--
Oli

[Alkimake]

Re: Combination or Permutation question!

here the main problem begins. :)

if i control every each $v then execution goes and goes forever.
Actually i tried but i could not get combinations. Thanks for helping
but if you can notify the code to do combinations i would really like
to know. Thanks again.

[Alkimake]

Re: Combination or Permutation question!

here the main problem begins. :)

if i control every each $v then execution goes and goes forever.
Actually i tried but i could not get combinations. Thanks for helping
but if you can modify the code to do combinations i would really like
to know. Thanks again.

[samuele.coppede@gmail.com]

Re: Combination or Permutation question!

hi, Hi made this function

function crea_combinazin i(){
$arg =func_get_args( );
//print_r($arg);
foreach ($arg as $k => $v){
$args['array'][]=$v;
$args['lunghezza'][]=count($v);
}

$max = count($arg);
for($i=0;$i<$ma x;$i++){
if($i==$max){
}else{
$str0 .= '
for($n'.$i.'=0; $n'.$i.'<'.coun t($args['array'][$i]).';$n'.$i.'++) {';
}
}
for($i=0;$i<$ma x;$i++){
// $str1 .= 'echo $args[\'array\']['.$i.'][$n'.$i.']; ';
$str1 .= '$testar[$indice][]= $args[\'array\']['.$i.'][$n'.$i.'];
';
if($i==($max-1)){
// $str1 .='echo \'<br>\';';
$str1 .='$indice++;';
for($i=0;$i<$ma x;$i++){
$str1 .= '}';
}
}else{
// $str1 .='echo \'-\';';
}
}
$all = '$indice=0;'.$s tr0.$str1;
eval($all);
//print_r($testar );
//echo $str1;
return($testar) ;
}

it get in input some array like
$ar1= array('a','b',' c');
$ar2 = array('d','e',' f');

and return an array with all combination by input arrays (
ad,ae,af,bd.... ecc

Look if u can modify it for u

[Alkimake]

Re: Combination or Permutation question!

really thank you for your function. This could have been very useful
and i am sure it will be somewhere else (I try to do this too). But i
didn't work for the combinations. When function is given with 2 same
array ( like crea_combinazin i($numbers, $numbers)), the results include
elements such like 11,22,112,122,1 12233 etc. The main point is the
elimination of this kind of elements. I still can not find the
solution. Thanks for helping.

[Oli Filth]

Re: Combination or Permutation question!

Alkimake said the following on 29/03/2006 09:36:[color=blue]
> here the main problem begins. :)
>
> if i control every each $v then execution goes and goes forever.
> Actually i tried but i could not get combinations. Thanks for helping
> but if you can modify the code to do combinations i would really like
> to know. Thanks again.[/color]

I'll give you a clue (because I'm mean ;) ).

In getPermutations (), the next layer of recursion is being passed the
current array, bit with the current value of the foreach loop removed.

To make a getCombinations (), you'll need to pass only items to the right
of the current foreach value.

You can do this by altering two lines of code in the function I gave you...


--
Oli

[Alkimake]

Re: Combination or Permutation question!

Here is the answer that Oli found :)

function getCombinations ($values)
{
$perms = array(null);
foreach ($values as $key => $v)
{
$temp = $values;
for ($i=0; $i<=$key; $i++) {
unset($temp[$i]);
}
$newPerms = getCombinations ($temp);
foreach ($newPerms as $perm)
{
$perms[] = ($v . $perm);
}
}
return $perms;
}


By the way this code is perfect. i have never seen a solution like
this. Thank you very much Oli. And second thank is for making me think.
Actually i didn't want somebody to answer me completely because to
understand the algoritm is more more more important than copy & paste
for me. This is impressive.

Actually i did the combinations when i saw your message but it is about
120 lines :) and very slow.

Take care and see ya.

PS: if i had mistakes i am sorry cuz my english is not so good :)

[Oli Filth]

Re: Combination or Permutation question!

Alkimake said the following on 29/03/2006 13:28:[color=blue]
> Here is the answer that Oli found :)
>
> function getCombinations ($values)
> {
> $perms = array(null);
> foreach ($values as $key => $v)
> {
> $temp = $values;
> for ($i=0; $i<=$key; $i++) {
> unset($temp[$i]);
> }
> $newPerms = getCombinations ($temp);
> foreach ($newPerms as $perm)
> {
> $perms[] = ($v . $perm);
> }
> }
> return $perms;
> }
>[/color]


P.S.: array_splice()


--
Oli