Permutações de Array

[Andrey Knupp Vital 136]

Fala galera .. resolvi postar este desafio aqui, porque na verdade, é um assunto / idéia na qual testa nossa capacidade lógica em programação, ou não .. então, a proposta é gerar o número de permutações possíveis de um dado array, esse array deve ser limitado a 5 índices / valores , não importa se é numérico ou string os valores do array, apenas tem que ter a limitação, o motivo é, deixando a execução do código mais rápida, mas quem quiser limitar a 10 , 20 , e o seu código for tanto eficiente quanto aos postados, fique a vontade, mas lembre-se que deve ser pelo menos '5'

 

Array ( 1 , 2 , 3 , 4 , 5 ) 

 

Pra quem não sabe o significado da palavra 'Permutação' :seta: Clique aqui

 

E não deve conter valores falsos, nulos, ou vazios e não poderá ter valores repetidos .. o array retornado também deve ser gerado de forma multi-dimensional

 

Array
(
   [0] => Array
       (
           [0] => ?
           [1] => ?
           [2] => ?
           ...
       )
)

 

Para cada conjunto de combinações ..

 

Para desenvolvimento do algoritmo, estão proibidas às bibliotecas BC Math , GMP, e o prazo é de 1 semana, os códigos podem ser postados neste mesmo tópico , na conclusão / ( código completo ) , os códigos que foram enviados, serão discutidos em relação ao outro ( ou não )

 

As formas de avaliações de cada código, será

1. Menos Loops
   
2. Coisas desnecessárias aplicadas desnecessáriamente fugindo do objetivo
   
3. Tempo de execução
   

 

Sobre 'coisas desnecessárias' eu quero dizer, coisas que podem ser substituídas por algo mais simples e que vai ter o mesmo resultado

 

Um abraço, e boa sorte ! dúvidas, só postarem aí !

 

Data de início :seta: 12 / 10 / 2011

Data de término:seta: 19 / 10 / 2011

[Bruno Augusto 417]

Não ficou faltando alguma coisa nesse desafio não?

 

Permutações, pelo que eu consegui aprender com meu péssimo professor do 3º. ano, precisa de dois números:

 

 

Ou sua idéia seria fazer com qualquer quantidade, tipo, a exemplo dos 5 elementos: 5 dois-a-dois, 5 três-a-três, 5 quatro-a-quatro e etc?

 

Seja qual for o caso eu ACHO que até já tenho pronto (em mente) como fazer...

[Andrey Knupp Vital 136]

Não .. permutação com dois números, é óbvia, por exemplo com 1 e 2 é o único resultado que você pode ter.

1 e 2 
2 e 1 

 

Ordem inversa .. a idéia e fazer com mais números .. por exemplo 1, 2 e 3

1 e 2 e 3 
2 e 1 e 3 
1 e 3 e 2 
3 e 1 e 2 
2 e 3 e 1 
3 e 2 e 1 

[Bruno Augusto 417]

Então cara, esses dois exemplos que você postou são Permutações de 2 números dois-a-dois e de 3 três-a-três.

 

De todo jeito existem dois valores: o número de elementos da permutação e de quanto em quanto será a dita cuja.

[Andrey Knupp Vital 136]

Entendi errado .. quando você falou '5 elementos: 5 dois-a-dois, 5 três-a-três, 5 quatro-a-quatro' esse 5 elementos, me confundiu a frase toda huaauhuah , e então, tem uma implementação, idéia aí na cuca ? rs

 

:assobiando:

[Eliseu M. 2]

Espere aí, acho que a confusão está no número de elementos repetidos. Pelo que entendi do desafio, eles deverão ser detectados pelo algoritmo e eliminados, e a respeito do número de elementos da permutação, no caso, a variável n, será definida após verificarmos se há valores repetidos, falsos, nulos ou vazios, o que sobrar entra no retorno.

 

Exemplo:

 

Array(1, "", 2, 2, "X", false);

Daí a permutação deve ocorrer nos elementos 1, 2 e X, somente. Tá certo?

[Andrey Knupp Vital 136]

Exatamente Eliseu .. isso aí, na verdade, essa funcionalidade tem que ser implementada para um processamento mais rápido do código, se já estamos limitando a 5 itens no array, imagina se estivéssemos um array com valores nulos , falsos ? de qualquer forma, eles incluem no processamento do código .. somente por isso .. não fica bom ter esses valores no array, sacou ?

^_^

[Eliseu M. 2]

Hmm, tudo bem, 5 itens, mas não será difícil fazer um benchmark com tão poucos items?

[Andrey Knupp Vital 136]

Não .. isso aí está bom, na verdade é uma quantidade rasoável em relação às possíveis .. pode ter mais quantidades no array .. mas aí cabe a sua imaginação pensar em quantas permutações você vai ter .. senão desequilibra na execução / processamento do código

[Eliseu M. 2]

Fiz uns testes em JS, com um algoritmo recursivo, o vetor de 5 items sempre deu 0ms, e é uma linguagem interpretada, meu Chrome travou somente com um vetor de 11 items.

 

Em Java, um vetor de 11 itens foi executado em +/- 2s. Meu processador pode ter contado muito, é um i7 2600, mesmo assim penso que vai ser difícil fazer bench com 5 itens.

 

Deixe uma média aí... de uns 7 ou 8 items, já que PHP é interpretado, e parece ser mais lento que a engine V8 do JavaScript o.O

[Andrey Knupp Vital 136]

Pois é .. por isso pode ser variado, isso depende da implementação de cada um .. 5 itens é o mínimo que tem que ter, no código que eu terminei de fazer para 7 items sendo ( 1 , 2 , 3 , 4 , 5 , 6 , 7 ) foi de 0.148540 ms , agora pra 8 permutações ( A , 1 , B , 2 , C , 3 , E , 4 ) foi de 0.3750 ms .. porem meu chrome apagou, consegui pegar o tempo de execução pelo terminal através do apacheBenchmark.

 

andrey@andrey:~$ ab -n 1 -c 1 http://127.0.0.1/index.php
This is ApacheBench, Version 2.3 <$Revision: 655654 $>
Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/
Licensed to The Apache Software Foundation, http://www.apache.org/

Benchmarking 127.0.0.1 (be patient).....done


Server Software:        Apache/2.2.14
Server Hostname:        127.0.0.1
Server Port:            80

Document Path:          /index.php
Document Length:        0 bytes

Concurrency Level:      1
Time taken for tests:   0.375 seconds
Complete requests:      1
Failed requests:        0
Write errors:           0
Total transferred:      295 bytes
HTML transferred:       0 bytes
Requests per second:    2.67 [#/sec] (mean)
Time per request:       375.000 [ms] (mean)
Time per request:       375.000 [ms] (mean, across all concurrent requests)
Transfer rate:          0.77 [Kbytes/sec] received

Connection Times (ms)
             min  mean[+/-sd] median   max
Connect:        0    0   0.0      0       0
Processing:   359  359   0.0    359     359
Waiting:      359  359   0.0    359     359
Total:        359  359   0.0    359     359

[Andrey Knupp Vital 136]

Bem .. como me deram o conselho de quem propõe o desafio, posta o primeiro código .. a minha solução é a seguinte ..

<?php 

 /**
  * Recupera todas permutações de uma matriz
  * 
  * Copyright (C) <2011-2012>  <Andrey Knupp Vital>
  *
  * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
  * the Free Software Foundation, either version 3 of the License, or
  * (at your option) any later version.
  *
  * This program is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
	  * You should have received a copy of the GNU General Public License
	  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
         * @author Andrey Knupp Vital
         * @param  Array   $Array 
  * @param  Array   $Permutations
         * @param  Integer $limitOffset
  * @throws LengthException se o número de índices / valores no array for maior que $limitOffset
         */
 function getPermutations ( Array $Array , Array $Permutations = Array ( ) , $limitOffset = 5 ) {
	   static $permutedItems = Array ( ) ;
	   $FlattenArray = Array ( );
	   forEach( new RecursiveIteratorIterator ( new RecursiveArrayIterator ( $Array ) ) as $Data ) 
		     $FlattenArray [ ] = $Data ; 
		     if( count( $FlattenArray ) > ( intval( $limitOffset ) ) ) 
			  throw new LengthException ( sprintf( 'Não podemos gerar permutações com mais de %d valores' , $limitOffset ) );
	   $Array = array_filter ( array_unique ( $FlattenArray ) ) ;
	   if( count ( $Array ) ) {
                         for ( $i = 0; $i < count ( $Array );  ++ $i ) {
			 $newArray = $Array ;
			 $newPermutations = $Permutations ;
			 array_push ( $newPermutations , array_shift ( array_splice ( $newArray , $i , 1 ) ) ) ;
			 getPermutations ( $newArray , $newPermutations , $limitOffset ) ;
		  } 
		  return $permutedItems;
	   } else $permutedItems [ ] = $Permutations;

 }

 

Utilizando ..

<?php
         require_once 'Permutations.php' ;
         echo '<pre>';
             print_r ( getPermutations ( Array ( 1 , 2 , 3 ) ) );
         echo '</pre>';

 

Saída:

Array
(
   [0] => Array
       (
           [0] => 1
           [1] => 2
           [2] => 3
       )

   [1] => Array
       (
           [0] => 1
           [1] => 3
           [2] => 2
       )

   [2] => Array
       (
           [0] => 2
           [1] => 1
           [2] => 3
       )

   [3] => Array
       (
           [0] => 2
           [1] => 3
           [2] => 1
       )

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

   [5] => Array
       (
           [0] => 3
           [1] => 2
           [2] => 1
       )

)

 

;)

 

Aguardo a implementação de vocês ..

[Kakashi_Hatake 267]

@Andrey Knupp

 

Na sua função, se for informado um espaço em branco vai ficar tosco.

 

print_r ( getPermutations ( Array ( 1 , 2, ' ' ) ) );

Array
(
   [0] => Array
       (
           [0] => 1
           [1] => 2
           [2] =>  
       )

   [1] => Array
       (
           [0] => 1
           [1] =>  
           [2] => 2
       )
continua...

 

 

Vou postar a minha solução para o desafio.

 

O máximo que consegui foi fazer permutações com até 8 valores, após isso dá pau no chrome <_< .

 

<?php
function permutations( array $array, $k = 0, $limit = 8 )
{
   static $filter;
   static $result;
   $k     = ( int ) $k;
   $limit = ( int ) $limit;
   if( $filter !== true )
   {
       $array  = array_unique(
                     array_filter(
                         $array,
                         function( $value )
                         {
                             $value = trim( $value );
                             return ( is_null( $value ) or empty( $value ) or is_bool( $value ) ) ? false : true;
                         }
                     )
                 );
       array_multisort( $array );
       $filter = true;
   }
   $count = count( $array );
   if( $count > $limit )
   {
       throw new LengthException( sprintf( 'Não podemos gerar permutações com mais de %d valores' , $limit ) );
   }
   if( $k == $count )
   {
       $result[ ] = $array;
   }
   else
   {
       for( $i = $k; $i < $count; $i++ )
       {
           list( $array[ $k ], $array[ $i ] ) = array( $array[ $i ], $array[ $k ] );
           permutations( $array, $k + 1 );
       }
   }
   return $result;
}
echo '<pre>';
print_r( permutations( array( 'A' , 1 , 'B' , 2 , 'C' , 3 , 'E' , 4 ) ) );

 

Saída(total de 40320)

Array
(
   [0] => Array
       (
           [0] => A
           [1] => B
           [2] => C
           [3] => E
           [4] => 1
           [5] => 2
           [6] => 3
           [7] => 4
       )

   [1] => Array
       (
           [0] => A
           [1] => B
           [2] => C
           [3] => E
           [4] => 1
           [5] => 2
           [6] => 4
           [7] => 3
       )
continua...

[Andrey Knupp Vital 136]

Carlos Coelho .. bacana sua implementação, mas tem um problema .. essas suas 8 permutações não chegam nem a mostrar resultado no benchmark, entra em loop infinito no navegador ..

 

O Problema do espaço da minha implementação pode ser resolvido facilmente ..

$FlattenArray [ ] = trim ( $Data ) ; 

 

;)

 

Obrigado por compartilhar seu algoritmo, cada código postado aqui serve de estudo para outras pessoas ..

Abraços

[Kakashi_Hatake 267]

Aqui funcionou, e eu testei várias vezes.

 

Em todo caso, fica o link para download do resultado gerado(total de 40320 combinações).

 

Download :seta: http://www.easy-share.com/E226A847FB9A4AE9A6C17E48179528C3/result.zip

 

EDIT

 

@Andrey Knupp

 

Eu acho que a verificação do número de elementos deveria ser feita após filtrar o array.

[Kakashi_Hatake 267]

pra 8 permutações ( A , 1 , B , 2 , C , 3 , E , 4 ) foi de 0.3750 ms .. porem meu chrome apagou, consegui pegar o tempo de execução pelo terminal através do apacheBenchmark.

 

Estranho <_< , testei aqui e deu um tempo bem maior.

 

C:\>ab -n 1 -c 1 http://127.0.0.1/test/getPermutations.php
This is ApacheBench, Version 2.3 <$Revision: 655654 $>
Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/
Licensed to The Apache Software Foundation, http://www.apache.org/

Benchmarking 127.0.0.1 (be patient).....done


Server Software:        Apache/2.2.17
Server Hostname:        127.0.0.1
Server Port:            80

Document Path:          /test/getPermutations.php
Document Length:        8456105 bytes

Concurrency Level:      1
Time taken for tests:   10.206 seconds
Complete requests:      1
Failed requests:        0
Write errors:           0
Total transferred:      8456271 bytes
HTML transferred:       8456105 bytes
Requests per second:    0.10 [#/sec] (mean)
Time per request:       10205.956 [ms] (mean)
Time per request:       10205.956 [ms] (mean, across all concurrent requests)
Transfer rate:          809.14 [Kbytes/sec] received

Connection Times (ms)
             min  mean[+/-sd] median   max
Connect:        0    0   0.0      0       0
Processing: 10204 10204   0.0  10204   10204
Waiting:     8160 8160   0.0   8160    8160
Total:      10204 10204   0.0  10204   10204

 

 

Já aproveitei e testei a minha :P

 

C:\>ab -n 1 -c 1 http://127.0.0.1/test/permutations.php
This is ApacheBench, Version 2.3 <$Revision: 655654 $>
Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/
Licensed to The Apache Software Foundation, http://www.apache.org/

Benchmarking 127.0.0.1 (be patient).....done


Server Software:        Apache/2.2.17
Server Hostname:        127.0.0.1
Server Port:            80

Document Path:          /test/permutations.php
Document Length:        8456105 bytes

Concurrency Level:      1
Time taken for tests:   4.255 seconds
Complete requests:      1
Failed requests:        0
Write errors:           0
Total transferred:      8456271 bytes
HTML transferred:       8456105 bytes
Requests per second:    0.24 [#/sec] (mean)
Time per request:       4255.052 [ms] (mean)
Time per request:       4255.052 [ms] (mean, across all concurrent requests)
Transfer rate:          1940.77 [Kbytes/sec] received

Connection Times (ms)
             min  mean[+/-sd] median   max
Connect:        0    0   0.0      0       0
Processing:  4253 4253   0.0   4253    4253
Waiting:     2213 2213   0.0   2213    2213
Total:       4253 4253   0.0   4253    4253

[Bruno Augusto 417]

Carlos, lembre-se que por estar num servidor local depende do hardware de processamento da máquina. E pelo que o Andrey andou demonstrando naquele tópico sobre lentidão num IPad, as dele são potentes.

 

Se eu pudesse rodar o AB aqui ( :cry: ) daria um valor significativamente maior ( :cry: ² ).

 

Mas enfim, esse negócio é cabuloso, mais do que imaginava. Pra fazer realmente com poucos loops e sem recursividade (até onde entendi), é uma matemática tenebrosa, algo chamado fatoradics.

[Kakashi_Hatake 267]

Carlos, lembre-se que por estar num servidor local depende do hardware de processamento da máquina. E pelo que o Andrey andou demonstrando naquele tópico sobre lentidão num IPad, as dele são potentes.

 

Pode ser isso, mas veja o tamanho do documento que ele testou

Document Length:        0 bytes

[Andrey Knupp Vital 136]

Carlos, o Document-Length ficou com zero, porque não dei o print ..

fiz apenas gerar as permutações não exibindo o resultado, entendeu ? daí não teve output ..

 

 

Eu acho que a verificação do número de elementos deveria ser feita após filtrar o array.

 

Não não .. a responsabilidade do usuário ( simulando um caso ) é enviar cinco items com valor , por isso mesmo foi estabelecida a regra pra limitar e filtrar os valores nulos , falsos, é um limite 5 independente deles serem inválidos ..

 

De qualquer forma, o array entra com os valores não permitidos , e saí com eles filtrados ..

 

;)

 

Se eu pudesse rodar o AB aqui ( :cry: ) daria um valor significativamente maior ( :cry: ² ).

 

Juro que não entendi .. até nesse pc aqui eu rodo o benchmark ..

 

 

Depende da sua definição para a palavra 'rodar'

[Kakashi_Hatake 267]

Desculpe a ignorância...

 

Executei o mesmo comando que você, só mudei o caminho para o arquivo.

 

ab -n 1 -c 1 http://127.0.0.1/index.php
ab -n 1 -c 1 http://127.0.0.1/test/getPermutations.php

 

Qual a diferença ?