Ir para conteúdo

Arquivado

Este tópico foi arquivado e está fechado para novas respostas.

Andrey Knupp Vital

Permutações de Array

Recommended Posts

Eu mandei a requisição para a index do servidor, que no caso era o arquivo que gerava as permutações, você mandou pra uma outra URL ..

Digite 'ab' que você vai ver todas as opções do benchmark.

 

Ignorância nada irmão .. você é gente fina ! qualquer coisa .. pode perguntar aí, estamos aí pro que der e vier !

 

;)

Compartilhar este post


Link para o post
Compartilhar em outros sites

Putz, ganhar por WO é sacanagem. :lol:

 

Mas eu bem que tentei viu, mas toda noite que sentava pra estudar um pouco melhor o assunto a cabeça até doía de tão maluco que é o negócio...

Compartilhar este post


Link para o post
Compartilhar em outros sites

Bom pelo menos ganhou né?

 

Agora... Vê se pega mais leve quando for criar o próximo desafio. O Andrey forçou a barra a tal ponto que meu tico e teco ainda estão se recuperando do trauma. :lol:

Compartilhar este post


Link para o post
Compartilhar em outros sites

Uma contribuição em código de browser (JS):

 

var result = [],
rI = 0; // criei fora para imprimir

function permuteArray(list, current) {

if (current === list.length) {
	result[rI] = [];
	for (var u = -1, l = list.length; ++u < l;) {
		result[rI][u] = list[u];
	}
	rI++;
	return;
}

for (var i = current - 1, l = list.length; ++i < l;) {
	var nextArray = list.slice(0);
	if (i !== current) {
		var n = nextArray[current];
		nextArray[current] = nextArray[i];
		nextArray[i] = n; // um swap
	}
	permuteArray(nextArray, current + 1);
}

}

console.time('maoe');
permuteArray([1,2,3], 0);
console.timeEnd('maoe');
console.log(result);

 

A função console.time() serve para fazer benchmark, não funciona em todos browsers. É, aqui não chega a 11 itens, mais que isso o browser trava. Testei no Chrome 15, IE9 e Chrome no Mac, não passa de 10. Permutação de 8 itens foi criada em 0.0025s e de 10 itens, em 0.39s. Em Java rodou o de 11 itens em 2s XD

 

Ah, esse loop meio estranho aí eu aprendi olhando algum desses feeds aí: http://www.google.co...bundle/frontend.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Com certeza o computador influencia, um perl roda voando aqui .. então .. no PERL 5.10 ..

 

my $start = time ;

sub permutation ( ) {
my ( $perm , @set ) = @_ ;
print "$perm\n" || return unless ( @set );
&permutation( $perm . $set[ $_ ] , @set[ 0..$_ - 1 ] , @set[ $_ + 1..$#set ] ) foreach ( 0..$#set );
}

@input = ( 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11  );

&permutation( '' , @input ) ;

my $end = time ;

print "Elapsed Time: " , ( $end - $start ) , " Seconds";

 

Saída:

andrey@andrey:~$ perl Permutations.pl
.... // ... alguns números ...
Elapsed Time: 8 Seconds

 

O Meu em java ficou assim ..

 

package permutation;
import java.util.Arrays;

public class Permutation {

      private static void getPermutations ( int [ ] Array , int [ ] Permutations ) {
             if ( Array.length == 0 ) {
                    System.out.println ( Arrays.toString ( Permutations ) );
             } else {
                    Integer Size = Array.length;
                    for ( int i = 0 ; i < Size ; ++ i ) {
                           int [ ] sArray = new int [ ( Size - 1 ) ];
                           int [ ] sPermutations = new int [ Permutations.length + 1 ];
                           System.arraycopy ( Permutations , 0 , sPermutations , 0 , Permutations.length );
                           for ( int k = 0, j = 0 ; k < Size ; ++ k ) {
                                  if ( k == i ) {
                                         sPermutations [ sPermutations.length - 1 ] = Array [ i ];
                                  } else sArray [ ++ j ] = Array [ k ];
                           }
                           getPermutations ( sArray , sPermutations );
                    }
             }
      }

      private static void permutation ( int ... x ) {
             getPermutations ( x , new int[ 0 ] );
      }

      public static void main ( String[] args ) {
             permutation ( 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ) ;
      }
}

 

Pra 8 argumentos ( inteiros ) , demorou 2 segundos .. agora, pode fazer com string .. array .. seguindo a idéia a cima, fica a critério de cada um agora ..

 

Valeu pela contribuição aí galera, mesmo já tendo ultrapassado a data, pra estudos, os códigos servem !

 

Abraços.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Bom, não ia postar.

 

Meu conhecimento no assunto é limitadíssimo e, na bem da verdade, eu não procuro sequer entender como isso funciona (ou deveria funcionar). Sou o Porquinho Prático da família :lol:

 

Enfim...

 

Esse código não presta por porr...caria nenhuma. Não computa todas as possibilidades, deixa de computar outras óbvias e nem tente colocar números maiores que dez. Ele simplesmente para de iterar no nove :yay:

 

Mas o Andrey insistiu... :closedeyes:

 

class Combinations implements Iterator {

   /**
    * Initial/ Current Position
    * 
    * @var	integer	$c
    */
   private $c = 0;

   /**
    * Combination Elements
    * 
    * @var	array	$n
    */
   private $n = array();

   /**
    * Per Combinations Amount
    * 
    * @var	integer	$r
    */
   private $r;

   /**
    * Combination Limit
    * 
    * @var	integer	$l
    */
   private $l;

   /**
    * Combinations Constructor
    * 
    * @param	array	$n
    * @param	integer	$r
    */
   public function __construct( array $n, $r ) {

       $this -> n = $n;

       $this -> r = (int) $r;

       $this -> l = ( $this -> factorial( count( $n ) ) / $this -> factorial( count( $n ) - $r ) );
   }

   // Iterator Interface Methods Implementation

   public function current() {

       $sequence = array();

       $length = count( $this -> n );

       for( $i = 0; $i < $length; $i += 1 ) {

           if( pow( 2, $i ) & $this -> c ) {

               $sequence[] = $this -> n[ $i ];
           }
       }

       $total = count( $sequence );

       if( $total != 0 && $total == $this -> r ) {

           $sequence = array_unique( array_merge( $sequence, array_reverse( $sequence ) ) );

           if( $total == 1 ) {

               return sprintf( '[%s]', implode( ', ', $sequence ) );

           } else {

               return sprintf( '[%s], [%s]', implode( ', ', $sequence ), implode( ', ', array_reverse( $sequence ) ) );
           }
       }
   }

   public function key() {
       return $this -> c;
   }

   public function next() {
       $this -> c += 1;
   }

   public function rewind() {
       $this -> c = 0;
   }

   public function valid() {
       return ( $this -> c < $this -> l );
   }

   // Auxiliar Methods

   private function factorial( $x ) {
       return $x <= 2 ? $x : $x * $this -> factorial( $x - 1 );
   } 
}

foreach( new Combinations( range( 1, 5 ), 2 ) as $combination ) {

   print '<pre>'; print_r( $combination );
}

Compartilhar este post


Link para o post
Compartilhar em outros sites

Como assim "montante de combinações", não entendi. :huh:

 

Não seria essa a fórmula de permitações ($this -> l)?

 

Sobre o "swap", você se refere a, por exemplo, 1;2 e 2;1? Se for eu fiz isso, no else do método current().

 

Eu não entendo o porquê esse trço não funciona como deveria :lol:

Compartilhar este post


Link para o post
Compartilhar em outros sites

Caros colegas, entrando (aproveitando) a disputa de vocês (revivendo essa publicação), me deparei com um desafiou.

 

Como faria para funcionar assim:

 

getCombinacoes(array(1,2,3,4,5), 2);

1 2

1 3

1 4

1 5

2 1

2 3

2 5

 

getCombinacoes(array(1,2,3,4,5), 3);

1 2 3

3 4 2

5 4 1

1 4 3

 

todas as combinações possiveis.

 

ainda vou além, como faria pra gerar as combinações possiveis com repetção:

 

getCombinacoesRep(array(1,2,3,4,5), 3);

1 1 1

2 2 2

1 1 2

1 2 2

3 3 3

4 4 4

5 5 5

5 3 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

×

Informação importante

Ao usar o fórum, você concorda com nossos Termos e condições.