• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

karva

[Duvida] Todas as combinacoes possiveis com um charset.

10 mensagens neste tópico

Boas.

Por exemplo, tenho uma array com várias letras, por exemplo:

$a = array('a', 'b', 'c', 'd');

etc...

Alguem sabe como é que pegando nessa array, seja criada uma nova com todas as combinacoe possiveis?

Ex:

//com a array usada la em cima, ficaria algo do tipo
$r = array('abcd','abdc','acbd','acdb','adbc','adcb',etc...);

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Posso te identificar o padrão de permutações para ver se entendes:

a b c d

      x

a b d c

    x

a d b c

      x

a d c b

    x

a c d b

      x

a c b d

  x

c a b d

etc.

com saltos em permutações n! se n=4 => 4! = 4x3x2x1

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

tenho uma função em Haskell que faz isso... mas não percebo o suficiente de php para a converter ;), de qualquer forma fica aqui, talvez ajude...

comb "" = [""]
comb l = let l1 = map aux1 [(x,delete x l) | x <- l]
             l2 = map aux2 l1
         in concat l2
    
aux1 (x,y) = (x,comb y)

aux2 (c,l) = [c:xs | xs <- l]

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Rui Carlos, podes explicar-me essa função?

a tua dúvida é na sintaxe da linguagem ou no algoritmo?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Rui Carlos, podes explicar-me essa função?

a tua dúvida é na sintaxe da linguagem ou no algoritmo?

Algoritmo ;)
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

pegamos num conjunto de letras, por exemplo {a,b,c} e criamos o conjunto { (a,{b,c}), (b,{a,c}), (c,{a,b}) }  ==> [(x,delete x l) | x <- l]

depois aplicamos a função recursivamente ao {b,c}, ao {a,c} e ao {a,b}, que vai produzir {{b,c},{c,b}}, {{a,c},{c,a}}, .....  ==> map aux1

depois disto já teremos

{ (a,{{b,c},{c,b}}), (b,{{a,c},{c,a}}), (c,{{a,b},{b,a}}) }

então voltamos a juntar o elemento que retiramos a cada conjunto

{ {{a,b,c},{a,c,b}}, {{b,a,c},{b,c,a}}, {{c,a,b},{c,b,a}} }   ==> map aux2

e depois juntamos os vários conjuntos

{ {a,b,c},{a,c,b}, {b,a,c},{b,c,a}, {c,a,b},{c,b,a} }

penso que já dá para ter uma ideia  ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

[table]

[td]Conjunto Z[/td]

[td]Z = {A, B, C}[/td]

[td]n = 3[/td]

[td]N° de elementos dos Grupos[/td]

[td]k = 2[/td]

[td]Taxa de 2 elementos[/td]

[td]Grupos de Combinação Simples[/td]

[td]{AB, AC, BC}[/td]

[td]Cn,k[/td]

[td]Fórmula de Cálculo[/td]

[td]Cn,k = n! / k!(n-k)![/td]

[td]C3,2 = 3! / 2!(3-2)! = 3[/td]

[/table]

em php ...

function collections($array=array(), $stopAt=0){
   if(!is_array($array) || !sizeof($array))
   {return false;}
   $arrayLength=sizeof($array);
   $stopAt=(($stopAt && $stopAt>$arrayLength) || !$stopAt)? $arrayLength:(integer)$stopAt;

   $output=array();
   $builder=array();
   $offset=0;
   for($b=0; $b<$arrayLength; $b++){
       $builder[]=array($b);
   }    

   do{
       $offset=sizeof($output);
       $builderLength=sizeof($builder);
       for($b=0; $b<$builderLength; $b++){
           for($bb=$builder[$b][sizeof($builder[$b])-1]+1; $bb<$arrayLength; $bb++){
               $output[]=array_merge($builder[$b], array($bb));
           }
       }
       $builder=array_slice($output, $offset);
   }while(sizeof($output[ sizeof($output)-1 ])<$stopAt);
   return (!$stopAt || $stopAt===sizeof($array))? $output: array_slice($output, $offset);
}

uso  para combinações de 3:

$foo=collections(array(0,1,2,3,12), 3);

Nota: São combinações e não permutações.

uso  para combinações de 4:

$foo=collections(array(0,1,2,3,12), 4);

Minimo de combinações =2, se não passares o nr de elementos a combinar, então gera de 2, 3, 4, 5....etc etc.

o array gerado tem as posições do array inicial.

ou seja :

$foo=Array ([0] => 1,[1] => 3,[2] => 4)

a combinação sera a posição 1, 3 e 4 do array original.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nota: São combinações e não permutações.

O que é que são combinações e não permutações?

Ainda não percebi o que é que fizeste, mas o que ele quer, tendo em conta o exemplo apresentado, é as permutações de um conjunto (visto que a ordem dos elementos é tida em conta).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nota: São combinações e não permutações.

o que é que são combinações e não permutações!?!

ainda não percebi o que é que fizeste, mas o que ele quer, tendo em conta o exemplo apresentado, é as permutações de um conjunto (visto que a ordem dos elementos é tida em conta!!).

tens razão. o exemplo apresentado por ele refere-se a permutações.

o codigo fornecido por mim calcula combinações.

hum.... assim ás 3 pancadas...

$str = "ABCDEFGH";
for($i=0;$i<strlen($str);$i++)
   $char_arr[] = $str{$i};

foreach ($char_arr as $x)
 foreach ($char_arr as $y)
    foreach ($char_arr as $w)
      foreach ($char_arr as $z)
       $permutate_arr[] = $x . $y . $w . $z;

permutações de 4 elementos.

/ing

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora