# Code-Golf: Permutations

Write a function that takes as input a set of integers (can be a list, array or any other container with distinct numbers), and outputs the list of all its permutations.

Python (95 chars):

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

It'd be nice to be beaten in the same language, but implementations in other languages are more than welcome!

## Python - 76 chars

Longer than gnibbler's, but implements things from scratch.

p=lambda x:x and[[a]+b for a in x for b in p([c for c in x if c!=a])]or[[]]

• I like the usage of comprehensions here. It really simplifies the code I posted a lot! – zxul767 Mar 6 '12 at 9:09

# Python, 52

Input is a set. Output is a list of lists.

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


This is shorter than the answer that does all the work with a builtin.

## J, 11 characters

(i.@!@#A.[)


Usage:

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


Explanation:

i.@!@# uses three verbs to return a list from 0 to (!n)-1 where n is the number of items in the given list.

[ returns the list itself. In the example shown that gives 0 1 2 3 4 5 A. 1 3 5.

A. returns one possible permutation of the second list for each item in the first list (kind of - the proper explanation is given here).

## Python - 55 chars

from itertools import*
p=lambda x:list(permutations(x))

• Not exactly what I was hoping folks would write... but it's useful to know Python has such utilities in the standard library. – zxul767 Mar 6 '12 at 9:15
• @zxul767: Why reinvent the wheel? Using the standard library will prove incredibly efficient... (and in this case makes for concise code when golfing ;-) – ChristopheD Mar 6 '12 at 15:19

p[]=[[]]
p l=[e:r|e<-l,r<-p$filter(/=e)l]  Essentially the same as ugoren's solution, but Haskell is better at list comprehensions! Of course, it can also do ## 30 import Data.List p=permutations  More efficient approach, that doesn't require an equality comparison: ## 92 import Data.List p[]=[[]] p l=(\(l,(e:r))->map(e:)$p(l++r))=<<(init$zip(inits l)(tails l))  As a consequece, this one also works when there are duplicate elements in the list. • The best part of this is that the 44 line haskell solution with the list comprehension is shorter than the python solution that just uses the standard library. – monadic Mar 30 '12 at 0:32 • p=Data.List.permutations. It feels like cheating, though. Also, Data.List.permutations doesn't output the permutations in lexicographic order. – John Dvorak Apr 9 '14 at 12:13 • You can write p[]=[[]] as a base case instead, saving two bytes. – Lynn Sep 10 '15 at 6:55 • @Mauris: right! I somehow assumed that the empty list would have zero permutations by definition, but since 0! = 1 that clearly doesn't make any sense. Having an empty base case is much nicer. – ceased to turn counterclockwis Sep 10 '15 at 10:54 ## in Q (48) g:{$[x=1;y;raze .z.s[x-1;y]{x,/:y except x}\:y]}


Sample usage:

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


# Ruby - 23 chars

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


for example f[[1,2,3]] outputs this.

but using [].permutation feels like cheating, so:

# Ruby - 59 chars

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


tested with

100.times.all?{arr=(1..99).to_a.sample(rand(5)); arr.permutation.to_a==f[arr]}
=> true

• If you want, you can demo your code using a site like IdeOne: ideone.com/crvtD – Mr. Llama Mar 6 '12 at 17:03
• Why would using built-in language features be cheating? – Mark Thomas Mar 8 '12 at 0:46
• @Mark maybe not cheating, but not much fun either, to write a function that just calls a built-in function. Like for example: "write a function to sort an array" -> f(array) { return array.sort(); } – jsvnm Mar 8 '12 at 13:02

Python - 58 chars

Slightly shorter than ugoren's, by taking a set as input:

p=lambda x:x and[[y]+l for y in x for l in p(x-{y})]or[[]]


# C, 270243 239 characters

#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;}


The function P(n,a) returns a pointer to the n! permutations of a, packed one after another in one giant array.

• Some tips: <malloc.h> isn't needed (ignore the warnings). sizeof n is 4 (portability is nice, but shorter is nicer). Use extra parameters as variables (e.g. p(n,a,N,i)). int*p(..)int*a,o;. Using global variables instead of parameters and return values often helps. – ugoren Nov 12 '12 at 21:48
• @ugoren, thanks for the tips. So far, I haven't seen how to shave any further characters using globals. (And hey, the function is thread-safe as it is!) – Michael Radford Nov 13 '12 at 22:51

# K, 30 bytes

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


No builtins!

## JS - 154 146 chars

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,y.slice(l))));}):a=[x];return a}

Test : f([1,2,3,4,5]).map(function(a){return a.join('')}).join('\n') returns this.

## R

Since we are talking about permutations let me show at least one solution in R:

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


## Perl 188

No library routines, no recursion

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]}}  ### Scala 30: def p(s:Seq[_])=s.permutations  ### Scala 195, quick'n'dirty, without permutations from library: 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, full grown, type safe iterator: 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)  ## Python - 50 chars import itertools list(itertools.permutations("123"))  • Why would this be downvoted 5 years later? – Jared Burrows Nov 10 '17 at 21:15 # Pyth, 4 bytes L.pb  Yeah, Pyth was created after this challenge was posted and all. This is still really cool. :D Live demo. Reading from stdin is a byte shorter: .pQ  # JavaScript 143136134 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> • I think you could gain 8 bytes by doing : js function p(s,a="",c="",i,z=[]){ instead of js function p(s,a,c,i,z){if(!z)a=c="",z=[] – ColdK Mar 26 '18 at 13:49 • Thanks ColdK. It worked and now is 8 bytes shorter. – wolfhammer Mar 31 '18 at 7:52 # Brachylog, 2 bytes pᵘ  Try it online!  ᵘ Find every unique p permutation of the input.  # Python, 53 bytes from itertools import*;lambda x:list(permutations(x))  • This is basically a duplicate of another submitted answer. I assume you came up with it independently (and you golfed it better), but I thought it was worth pointing out the duplicate. – user62131 Nov 23 '16 at 5:50 # Jelly, 2 bytes Œ!  Try it online! Yay for builtins! # K (oK), 3 bytes Solution prm  Try it online! Explanation: It's a 3 byte built-in shortcut to the following built-in 47 byte function: {[x]{[x]$[x;,/x ,''o'x ^/:x;,x]}@$[-8>@x;!x;x]}  ... which can be shortened to 23 bytes if we know we're getting a list of ints as input: {$[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)


# Axiom, 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)


ungolfed

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


All this call one library function that give permutation on index (only integers as permutation as permutations on , permutations on [1,2], permutations on[1,2,3] etc).So it is enough get these set of indices and build the lists; One has to note that this seems to be compiled good for every List of type 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

• Do you have a link to the Axiom interpreter? I'd love to get it added to Try It Online!, it looks like an interesting language. – caird coinheringaahing Feb 26 '18 at 20:18

# Japt, 1 byte

á


Japt interpreter

This got bumped and didn't have a Japt answer, so I figured I'd go ahead and add one. á when applied to an array and without any arguments is the builtin for "get all permutations". The -R flag used in the interpreter link only modifies how the result is printed.

# APL(NARS), 39 chars, 78 bytes

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


test:

  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'


# 05AB1E - 2 1 bytes

œ

The input must be an array/list.

Explanation:

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

Saved a byte thanks to Erik the Outgolfer

• You can take input as a single list, no need to take it separated by newlines. – Erik the Outgolfer Oct 20 '18 at 19:45
• Thank you! I can now shorten this to one byte! – MilkyWay90 Oct 20 '18 at 19:47