Code-Golf: Permutações

21

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

p=lambda s:s and sum(map(lambda e:map(lambda p:[e]+p,p(filter(lambda x:x!=e,s))),s),[]) or [[]]

Seria bom ser derrotado no mesmo idioma, mas implementações em outros idiomas são mais que bem-vindas!

zxul767
fonte

Respostas:

10

Python - 76 caracteres

Mais do que o roedor, mas implementa coisas do zero.

p=lambda x:x and[[a]+b for a in x for b in p([c for c in x if c!=a])]or[[]]
Ugoren
fonte
Eu gosto do uso de compreensões aqui. Simplifica muito o código que publiquei bastante!
Zxul767 6/03/12
16

Python, 52

Entrada é um conjunto. Saída é uma lista de listas.

f=lambda a:[p+[x]for x in a for p in f(a-{x})]or[[]]

Isso é mais curto que a resposta que faz todo o trabalho com um builtin .

feersum
fonte
9

J, 11 caracteres

(i.@!@#A.[)

Uso:

   (i.@!@#A.[) 1 3 5
1 3 5
1 5 3
3 1 5
3 5 1
5 1 3
5 3 1

Explicação:

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

Gareth
fonte
Forneça um link para informações sobre J?
Sparr
1
@Sparr O site J possui alguns bons guias - Aprendendo J e J para programadores C - e uma página que cobre o vocabulário .
Gareth
8

Python - 55 caracteres

from itertools import*
p=lambda x:list(permutations(x))
mordedor
fonte
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
4
@ 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 ;-)
ChristopheD
8

Haskell, 44 43

p[]=[[]]
p l=[e:r|e<-l,r<-p$filter(/=e)l]

Essencialmente o mesmo que a solução da ugoren, mas Haskell é melhor na compreensão de listas!


Claro, também pode fazer

30

import Data.List
p=permutations


Abordagem mais eficiente, que não requer uma comparação de igualdade:

92

import Data.List
p[]=[[]]
p l=(\(l,(e:r))->map(e:)$p(l++r))=<<(init$zip(inits l)(tails l))

Como conseqüência, este também funciona quando há elementos duplicados na lista.

deixou de girar contra-relógio
fonte
4
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 #
1
Você pode escrever p[]=[[]]como um caso base, salvando dois bytes.
Lynn
@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
3

em Q (48)

g:{$[x=1;y;raze .z.s[x-1;y]{x,/:y except x}\:y]}

Uso da amostra:

q)g[3;1 2 3]
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
sinedcm
fonte
2

Ruby - 23 caracteres

f=->x{p *x.permutation}

por exemplo, f[[1,2,3]] gera isso .

mas usar [].permutationparece trapaça, então:

Ruby - 59 caracteres

f=->a{a.size<2?[a]:a.flat_map{|x|f[(a-x=[x])].map{|y|x+y}}}

testado com

100.times.all?{arr=(1..99).to_a.sample(rand(5)); arr.permutation.to_a==f[arr]}
=> true
jsvnm
fonte
Se você quiser, você pode demonstrar seu código usando um site como IdeOne: ideone.com/crvtD
Mr. Llama
1
Por que usar recursos de linguagem embutidos seria trapaceiro?
Mark Thomas
@ 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
2

Python - 58 caracteres

Um pouco menor que o de ugoren, tomando um conjunto como entrada:

p=lambda x:x and[[y]+l for y in x for l in p(x-{y})]or[[]]
Jules Olléon
fonte
2

C, 270 243 239 caracteres

#define S t=*a;*a=a[i];a[i]=t;
#define R o=p(n,r-1,a+1,o,r-2,0)
int*p(n,r,a,o,i,t)int*a,*o;{if(!r)for(;n;--n)*o++=*--a;else{R;for(;i;--i){S R;S}}return o;}
P(n,a)int*a;{int N=1,i=n;for(;i;N*=i--);return p(n,n,a,malloc(N*n*8),n-1,0)-N*n;}

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.

Michael Radford
fonte
1
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
@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 é!)
Michael Radford
2

K, 30 bytes

{x@v@&((#x;1)~^=:)'v:!(#x)##x}

Sem builtins!

kirbyfan64sos
fonte
1

JS - 154 146 caracteres

function f(x){var a=[],m;(m=x.length)>1?f(x.slice(1)).map(function(y){for(l=m;l--;a.push(y.slice(0,l).concat(x[0],y.slice(l))));}):a=[x];return a}

Teste: f([1,2,3,4,5]).map(function(a){return a.join('')}).join('\n')retorna isso .

JiminP
fonte
1

R

Como estamos falando de permutações, deixe-me mostrar pelo menos uma solução em R:

library(gtools);v=c(3,4,5);permutations(length(v),length(v),v)
Paolo
fonte
1

Perl 188

Sem rotinas de biblioteca, sem recursão

sub p{$l=(@_=sort split'',shift)-1;while(print@_){$k=$j=$l;--$k while($_[$k-1]cmp$_[$k])>=0;$k||last;--$j while($_[$k-1]cmp$_[$j])>=0;@_[$j,$k-1]=@_[$k-1,$j];@_[$k..$l]=reverse@_[$k..$l]}}
novo
fonte
1

Scala 30:

def p(s:Seq[_])=s.permutations 

Scala 195, quick'n'dirty, sem permutações da biblioteca:

def c(x:Int,t:List[_]):List[_]={val l=t.size
val o=x%l
if(l>1){val r=c(x/l,t.tail)
r.take(o):::(t.head::r.drop(o))}else
t}
def p(y:List[_])=(0 to(1 to y.size).product).foreach(z=>println(c(z,y)))

val y=List(0,1,2,3)
p(y)

Scala 293, adulto, tipo iterador seguro:

class P[A](val l:Seq[A])extends Iterator[Seq[A]]{
var c=0
val s=(1 to l.size).product
def g(c:Int,t:List[A]):List[A]={
val n=t.size
val o=c%n
if(n>1){val r=g(c/n,t.tail)
r.take(o):::(t.head::r.drop(o))
}else
t}
def hasNext=c!=s
def next={c+=1
g(c-1,l.toList)}
}
for(e<-new P("golf"))println(e)
Usuário desconhecido
fonte
1

Python - 50 caracteres

import itertools
list(itertools.permutations("123"))
Jared Burrows
fonte
Por que isso seria rebaixado 5 anos depois?
Jared Burrows
1

Pitão, 4 bytes

L.pb

Sim, Pyth foi criado depois que esse desafio foi lançado e tudo. Isso ainda é muito legal. : D

Demonstração ao vivo.

Ler a partir de stdin é um byte mais curto:

.pQ
kirbyfan64sos
fonte
1

Javascript 143 136 134 123

function p(s,a="",c="",i,z=[]){a+=c,i=s.length
!i?z.push(a):0
for(;i--;s.splice(i,0,c))p(s,a,c=s.splice(i,1),0,z);return z}

var perms = p([1,2,3]);

document.getElementById('output').innerHTML = perms.join("\n");
<pre id="output"></pre>

martelo de lobo
fonte
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=[]
ColdK
Obrigado ColdK. Funcionou e agora é 8 bytes mais curto.
31718 wolfhammer
1

Braquilog , 2 bytes

pᵘ

Experimente online!

 ᵘ    Find every unique
p     permutation of the input.
String não relacionada
fonte
0

Python, 53 bytes

from itertools import*;lambda x:list(permutations(x))
Oliver Ni
fonte
1
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.
0

K (oK) , 3 bytes

Solução

prm

Experimente online!

Explicação:

É um byte 3 embutido atalho para a seguinte embutido 47 função de bytes:

{[x]{[x]$[x;,/x ,''o'x ^/:x;,x]}@$[-8>@x;!x;x]}

... que pode ser reduzido para 23 bytes se soubermos que estamos recebendo uma lista de entradas como entrada:

{$[x;,/x,''o'x^/:x;,x]} / golfed built in
{                     } / lambda function with implicit input x
 $[ ;             ;  ]  / if[condition;true;false]
   x                    / if x is not null...
             x^/:x      / x except (^) each-right (/:) x; create length-x combinations
           o'           / call self (o) with each of these
       x,''             / x concatenated with each-each of these results (this is kinda magic to me)
     ,/                 / flatten list
                    ,x  / otherwise enlist x (enlisted empty list)
rua
fonte
0

Axioma, 160 bytes

p(a)==(#a=0=>[[]];r:=[[a.1]];r:=delete(r,1);n:=#a;m:=factorial n;m>1.E7=>r;b:=permutations n;for j in 1..m repeat(x:=b.j;r:=concat([a.(x.i)for i in 1..n],r));r)

destroçado

--Permutation of a
pmt(a)==
     #a=0=>[[]]
     r:=[[a.1]]; r:=delete(r,1) -- r has the type List List typeof(a)
     n:=#a
     m:=factorial n
     m>1.E7=>r
     b:=permutations(n)         --one built in for permutation indices 
     for j in 1..m repeat
        x:=b.j
        r:=concat([a.(x.i) for i in 1..n],r)
     r

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

(4) -> p([1,2,3])
   Compiling function p with type List PositiveInteger -> List List
      PositiveInteger
   (4)  [[1,2,3],[1,3,2],[3,1,2],[2,1,3],[2,3,1],[3,2,1]]
                                          Type: List List PositiveInteger
(5) -> p([x^2,y*x,y^2])
   Compiling function p with type List Polynomial Integer -> List List
      Polynomial Integer
   (5)
      2      2    2  2        2  2            2  2        2  2    2      2
   [[x ,x y,y ],[x ,y ,x y],[y ,x ,x y],[x y,x ,y ],[x y,y ,x ],[y ,x y,x ]]
                                       Type: List List Polynomial Integer
(6) -> p([sin(x),log(y)])
   Compiling function p with type List Expression Integer -> List List
      Expression Integer
   (6)  [[sin(x),log(y)],[log(y),sin(x)]]
                                       Type: List List Expression Integer
(7) -> m:=p("abc")::List List Character
   Compiling function p with type String -> Any
   (7)  [[a,b,c],[a,c,b],[c,a,b],[b,a,c],[b,c,a],[c,b,a]]
                                                Type: List List Character
(8) -> [concat(map(x+->x::String, m.j))  for j in 1..#m]
   (8)  ["abc","acb","cab","bac","bca","cba"]
                                                        Type: List String
RosLuP
fonte
Você tem um link para o intérprete Axiom? Eu adoraria adicioná-lo ao Try It Online! , parece um idioma interessante.
caird coinheringaahing
0

Japt , 1 byte

á

Intérprete Japt

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.

Kamil Drakari
fonte
0

APL (NARS), 39 caracteres, 78 bytes

{1≥k←≢w←,⍵:⊂w⋄↑,/{w[⍵],¨q w[a∼⍵]}¨a←⍳k}

teste:

  q←{1≥k←≢w←,⍵:⊂w⋄↑,/{w[⍵],¨q w[a∼⍵]}¨a←⍳k}
  q 1 2 3
1 2 3  1 3 2  2 1 3  2 3 1  3 1 2  3 2 1 
  q 'abcd'
abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba 
RosLuP
fonte
0

05AB1E - 2 1 byte s

œ

A entrada deve ser uma matriz / lista.

Explicação:

œ //Takes all the permutations of the elements in the top of the stack (the input is a list, so it would work)

Guardou um byte graças a Erik the Outgolfer

MilkyWay90
fonte
Você pode receber a entrada como uma lista única, sem precisar separá-la por novas linhas.
Erik the Outgolfer
Obrigado! Agora posso encurtar isso para um byte!
precisa