Code-Golf: Permutaciones

21

Escriba una función que tome como entrada un conjunto de enteros (puede ser una lista, matriz o cualquier otro contenedor con números distintos), y genera la lista de todas sus permutaciones.

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 [[]]

Sería bueno ser golpeado en el mismo idioma, ¡pero las implementaciones en otros idiomas son más que bienvenidas!

zxul767
fuente

Respuestas:

10

Python - 76 caracteres

Más largo que el de gnibbler, pero implementa cosas desde cero.

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
fuente
Me gusta el uso de las comprensiones aquí. ¡Realmente simplifica el código que publiqué mucho!
zxul767
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

Explicación:

i.@!@# usa tres verbos para devolver una lista de 0 a (! n) -1 donde n es el número de elementos en la lista dada.

[devuelve la lista en sí. En el ejemplo que se muestra da 0 1 2 3 4 5 A. 1 3 5.

A.devuelve una posible permutación de la segunda lista para cada elemento en la primera lista (tipo de - la explicación adecuada se da aquí ).

Gareth
fuente
Proporcione un enlace a información sobre J?
Sparr
1
@Sparr El sitio web de J tiene un par de buenas guías: Aprendizaje de J y J para programadores de C , y una página que cubre el vocabulario .
Gareth el
8

Python - 55 caracteres

from itertools import*
p=lambda x:list(permutations(x))
gnibbler
fuente
No es exactamente lo que esperaba que la gente escribiera ... pero es útil saber que Python tiene tales utilidades en la biblioteca estándar.
zxul767
44
@ zxul767: ¿Por qué reinventar la rueda? El uso de la biblioteca estándar resultará increíblemente eficiente ... (y en este caso es un código conciso al jugar al golf ;-)
ChristopheD
8

Haskell, 44 43

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

¡Esencialmente lo mismo que la solución de ugoren, pero Haskell es mejor en la comprensión de listas!


Por supuesto, también puede hacer

30

import Data.List
p=permutations


Enfoque más eficiente, que no requiere una comparación de igualdad:

92

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

Como consecuencia, este también funciona cuando hay elementos duplicados en la lista.

dejó de girar en sentido antihorario
fuente
44
La mejor parte de esto es que la solución de 44 líneas de haskell con la comprensión de la lista es más corta que la solución de Python que solo usa la biblioteca estándar.
monádico
p=Data.List.permutations. Sin embargo, se siente como hacer trampa. Además, Data.List.permutationsno genera las permutaciones en orden lexicográfico.
John Dvorak
1
En su lugar, puede escribir p[]=[[]]como un caso base, ahorrando dos bytes.
Lynn
@Mauris: ¡cierto! Supuse de alguna manera que la lista vacía tendría cero permutaciones por definición, ¡pero desde 0! = 1 que claramente no tiene ningún sentido. Tener una caja base vacía es mucho mejor.
dejó de girar en sentido antihorario el
3

en Q (48)

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

Uso de la muestra:

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
fuente
2

Ruby - 23 caracteres

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

por ejemplo da f[[1,2,3]] salida a esto .

pero usar se [].permutationsiente como hacer trampa, así que:

Ruby - 59 caracteres

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

probado con

100.times.all?{arr=(1..99).to_a.sample(rand(5)); arr.permutation.to_a==f[arr]}
=> true
jsvnm
fuente
Si lo desea, puede demostrar su código usando un sitio como IdeOne: ideone.com/crvtD
Mr. Llama
1
¿Por qué el uso de funciones de lenguaje incorporadas sería una trampa?
Mark Thomas
@ Mark quizás no haga trampa, pero tampoco es muy divertido escribir una función que solo llame a una función incorporada. Como por ejemplo: "escribir una función para ordenar una matriz" ->f(array) { return array.sort(); }
jsvnm
2

Python - 58 caracteres

Un poco más corto que el de ugoren, tomando un conjunto como entrada:

p=lambda x:x and[[y]+l for y in x for l in p(x-{y})]or[[]]
Jules Olléon
fuente
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;}

La función P (n, a) devuelve un puntero a la n! permutaciones de a, empaquetadas una tras otra en una matriz gigante.

Michael Radford
fuente
1
Algunos consejos: <malloc.h> isn't needed (ignore the warnings). sizeof n` es 4 (la portabilidad es agradable, pero más corta es mejor). Utilice parámetros adicionales como variables (p p(n,a,N,i). Ej .). int*p(..)int*a,o;. El uso de variables globales en lugar de parámetros y valores de retorno a menudo ayuda.
Ugoren
@ugoren, gracias por los consejos. Hasta ahora, no he visto cómo afeitarme más personajes usando globals. (¡Y oye, la función es segura para subprocesos como es!)
Michael Radford
2

K, 30 bytes

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

No hay construcciones!

kirbyfan64sos
fuente
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}

Prueba: f([1,2,3,4,5]).map(function(a){return a.join('')}).join('\n')devuelve esto .

JiminP
fuente
1

R

Como estamos hablando de permutaciones, permítanme mostrar al menos una solución en R:

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

Perl 188

Sin rutinas de biblioteca, sin recursividad

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]}}
ardnew
fuente
1

Scala 30:

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

Scala 195, quick'n'dirty, sin permutaciones de la 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, completo, tipo seguro de iterador:

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)
usuario desconocido
fuente
1

Python - 50 caracteres

import itertools
list(itertools.permutations("123"))
Jared Burrows
fuente
¿Por qué se rechazaría esto 5 años después?
Jared Burrows
1

Pyth, 4 bytes

L.pb

Sí, Pyth se creó después de publicar este desafío y todo. Esto sigue siendo realmente genial. :RE

Demo en vivo.

Leer de stdin es un byte más corto:

.pQ
kirbyfan64sos
fuente
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>

martillo de lobo
fuente
Creo que podría ganar 8 bytes haciendo: en js function p(s,a="",c="",i,z=[]){ lugar de js function p(s,a,c,i,z){if(!z)a=c="",z=[]
ColdK
Gracias ColdK Funcionó y ahora es 8 bytes más corto.
Wolfhammer
0

Python, 53 bytes

from itertools import*;lambda x:list(permutations(x))
Oliver Ni
fuente
1
Esto es básicamente un duplicado de otra respuesta enviada . Supongo que se le ocurrió de forma independiente (y lo jugó mejor), pero pensé que valía la pena señalar el duplicado.
0

K (oK) , 3 bytes

Solución

prm

Pruébalo en línea!

Explicación:

Es un acceso directo integrado de 3 bytes a la siguiente función integrada de 47 bytes:

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

... que se puede acortar a 23 bytes si sabemos que estamos obteniendo una 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)
callejero
fuente
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)

sin golf

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

Todo esto llama a una función de biblioteca que proporciona permutación en el índice (solo enteros como permutación como permutaciones en [1], permutaciones en [1,2], permutaciones en [1,2,3] etc.). Por lo tanto, es suficiente obtener estos conjuntos de índices y construir las listas; Hay que tener en cuenta que esto parece compilarse bien para cada lista de 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
fuente
¿Tiene un enlace al intérprete de Axiom? ¡Me encantaría agregarlo a Probar en línea! , parece un lenguaje interesante.
caird coinheringaahing
0

Japt , 1 byte

á

Intérprete japonés

Esto se golpeó y no tenía una respuesta de Japt, así que pensé en seguir adelante y agregar una. ácuando se aplica a una matriz y sin ningún argumento es el incorporado para "obtener todas las permutaciones". El -Rindicador utilizado en el enlace del intérprete solo modifica cómo se imprime el resultado.

Kamil Drakari
fuente
0

APL (NARS), 39 caracteres, 78 bytes

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

prueba:

  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
fuente
0

05AB1E - 2 1 byte s

œ

La entrada debe ser una matriz / lista.

Explicación:

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

Salvó un byte gracias a Erik the Outgolfer

MilkyWay90
fuente
Puede tomar la entrada como una sola lista, no es necesario tomarla separada por nuevas líneas.
Erik the Outgolfer
¡Gracias! ¡Ahora puedo acortar esto a un byte!
MilkyWay90