Publicado em 12 de out.

Permutações de Array

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á

Menos Loops

Coisas desnecessárias aplicadas desnecessáriamente fugindo do objetivo

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

Discussão (35)

Entre ou cadastre-se para participar da discussão

Entrar Criar conta

Bruno Augusto· 12 de out.

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:

/applications/core/interface/imageproxy/imageproxy.php?img=http://upload.wikimedia.org/wikipedia/pt/math/0/1/e/01e94a1e8550f9bc3a33032cb2939c79.png&key=8f33c59dc9ce6062630b7f6892583b5347aa16ef891cb012399aa9e080618161" alt="01e94a1e8550f9bc3a33032cb2939c79.png" />

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· 12 de out.

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· 12 de out.

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· 12 de out.

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.· 12 de out.

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· 12 de out.

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.· 12 de out.

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

Andrey Knupp Vital· 12 de out.

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.· 13 de out.

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· 13 de out.

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· 14 de out.

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· 16 de out.

@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· 16 de out.

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· 16 de out.

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· 17 de out.

>
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· 17 de out.

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: 2 ).

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· 17 de out.

>
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· 17 de out.

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: 2 ).

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

/applications/core/interface/imageproxy/imageproxy.php?img=http://debiloide.com.br/wp-content/uploads/fotos_187_PC-Recauchutado-300x260.jpg&key=b6e59af1777a2111f9846e61be70053a05473f64fb1a237acb9b896f94bcd293" alt="fotos_187_PC-Recauchutado-300x260.jpg" />

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

Kakashi_Hatake· 17 de out.

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 ?

Andrey Knupp Vital· 17 de out.

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 !

;)

Kakashi_Hatake· 20 de out.

Quem ganhou ?

:lol:

Andrey Knupp Vital· 20 de out.

Você, hauhauha , único que postou o código =) não teve concorrência.

Bruno Augusto· 21 de out.

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...

Andrey Knupp Vital· 21 de out.

Cara .. o negócio tá na lógica .. tão simples quanto isso ..

Kakashi_Hatake· 22 de out.

>
Putz, ganhar por WO é sacanagem. :lol:

Não foi fácil ganhar por WO. :lol: