Code-Golf: Permutações
Escreva uma função que tenha como entrada um conjunto de números inteiros (pode ser uma lista, matriz ou qualquer outro contêiner com números distintos) e produza a lista de todas as suas permutações.
Python (95 caracteres) :
Seria bom ser derrotado no mesmo idioma, mas implementações em outros idiomas são mais que bem-vindas!
Python - 76 caracteres
Mais do que o roedor, mas implementa coisas do zero.
Eu gosto do uso de compreensões aqui. Simplifica muito o código que publiquei bastante!
— Zxul767 6/03/12
Entrada é um conjunto. Saída é uma lista de listas.
Isso é mais curto que a resposta que faz todo o trabalho com um builtin .
J, 11 caracteres
i.@!@# usa três verbos para retornar uma lista de 0 a (! n) -1, em que n é o número de itens na lista fornecida.
[retorna a própria lista. No exemplo mostrado que dá 0 1 2 3 4 5 A. 1 3 5.
A.retorna uma permutação possível da segunda lista para cada item da primeira lista (tipo de - a explicação apropriada é dada aqui ).
Forneça um link para informações sobre J?
@Sparr O site J possui alguns bons guias - Aprendendo J e J para programadores C - e uma página que cobre o vocabulário .
Python - 55 caracteres
Não é exatamente o que eu esperava que as pessoas escrevessem ... mas é útil saber que o Python tem esses utilitários na biblioteca padrão.
@ zxul767: Por que reinventar a roda? Usando a biblioteca padrão irá revelar-se extremamente eficiente ... (e neste caso faz para código conciso ao golfe ;-)
Essencialmente o mesmo que a solução da ugoren, mas Haskell é melhor na compreensão de listas!
Claro, também pode fazer
Abordagem mais eficiente, que não requer uma comparação de igualdade:
Como conseqüência, este também funciona quando há elementos duplicados na lista.
A melhor parte disso é que a solução haskell de 44 linhas com a compreensão da lista é mais curta que a solução python que apenas usa a biblioteca padrão.
— monádico
p=Data.List.permutations. Parece trapaça, no entanto. Além disso, Data.List.permutationsnão gera as permutações em ordem lexicográfica.
— John Dvorak #
Você pode escrever p[]=[[]]como um caso base, salvando dois bytes.
@Mauris: certo! De alguma forma, assumi que a lista vazia teria zero permutações por definição, mas desde 0! = 1 que claramente não faz sentido. Ter uma base vazia é muito melhor.
— deixou de girar no sentido anti
em Q (48)
Ruby - 23 caracteres
por exemplo, f[[1,2,3]] gera isso .
mas usar [].permutationparece trapaça, então:
Ruby - 59 caracteres
Se você quiser, você pode demonstrar seu código usando um site como IdeOne: ideone.com/crvtD
Por que usar recursos de linguagem embutidos seria trapaceiro?
@ Mark talvez não trapaceie, mas também não seja muito divertido, para escrever uma função que apenas chama uma função interna. Como por exemplo: "escreva uma função para classificar uma matriz" ->f(array) { return array.sort(); }
— jsvnm 08/03/12
Python - 58 caracteres
Um pouco menor que o de ugoren, tomando um conjunto como entrada:
C, 270 243 239 caracteres
A função P (n, a) retorna um ponteiro para n! permutações de a, embaladas uma após a outra em uma matriz gigante.
Algumas dicas: <malloc.h> isn't needed (ignore the warnings). sizeof n` é 4 (portabilidade é boa, mas menor é melhor). Use parâmetros extras como variáveis ​​(por exemplo p(n,a,N,i)). int*p(..)int*a,o;. O uso de variáveis ​​globais em vez de parâmetros e valores de retorno geralmente ajuda.
@ugoren, obrigado pelas dicas. Até agora, eu não vi como fazer a barba de outros personagens usando globals. (E hey, a função é thread-safe como é!)
Sem builtins!
JS - 154 146 caracteres
Teste: f([1,2,3,4,5]).map(function(a){return a.join('')}).join('\n')retorna isso .
Como estamos falando de permutações, deixe-me mostrar pelo menos uma solução em R:
Sem rotinas de biblioteca, sem recursão
Scala 195, quick'n'dirty, sem permutações da biblioteca:
Scala 293, adulto, tipo iterador seguro:
Python - 50 caracteres
Por que isso seria rebaixado 5 anos depois?
Sim, Pyth foi criado depois que esse desafio foi lançado e tudo. Isso ainda é muito legal. : D
Ler a partir de stdin é um byte mais curto:
Eu acho que você poderia ganhar 8 bytes fazendo: js function p(s,a="",c="",i,z=[]){ em vez de js function p(s,a,c,i,z){if(!z)a=c="",z=[]
Obrigado ColdK. Funcionou e agora é 8 bytes mais curto.
— 31718 wolfhammer
Isso é basicamente uma duplicata de outra resposta enviada . Suponho que você o tenha elaborado de forma independente (e você jogou melhor), mas achei que valia a pena apontar a duplicata.
Yay para builtins!
K (oK) , 3 bytes
É um byte 3 embutido atalho para a seguinte embutido 47 função de bytes:
... que pode ser reduzido para 23 bytes se soubermos que estamos recebendo uma lista de entradas como entrada:
Axioma, 160 bytes
Tudo isso chama uma função de biblioteca que fornece permutação no índice (apenas números inteiros como permutação como permutações em [1], permutações em [1,2], permutações em [1,2,3] etc.). de índices e construir as listas; É preciso notar que isso parece ser compilado para todas as listas do tipo X
Você tem um link para o intérprete Axiom? Eu adoraria adicioná-lo ao Try It Online! , parece um idioma interessante.
Isso foi prejudicado e não tinha uma resposta em japonês, então imaginei que iria em frente e adicionaria uma. áquando aplicado a uma matriz e sem argumentos é o construtor para "obter todas as permutações". O -Rsinalizador usado no link do intérprete modifica apenas como o resultado é impresso.