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

• I've submitted a golfing suggestion to this answer which makes it shorter than your answer. Mar 14, 2021 at 18:50

## 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! Mar 6, 2012 at 9:09

## 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. Mar 6, 2012 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 ;-) Mar 6, 2012 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. Mar 30, 2012 at 0:32 • p=Data.List.permutations. It feels like cheating, though. Also, Data.List.permutations doesn't output the permutations in lexicographic order. Apr 9, 2014 at 12:13 • You can write p[]=[[]] as a base case instead, saving two bytes. – Lynn Sep 10, 2015 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. Sep 10, 2015 at 10:54 # 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. Nov 12, 2012 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!) Nov 13, 2012 at 22:51 • 215 bytes – c-- Aug 17, 2022 at 20:42 # Prolog (SWI), 33 bytes X-Y:-bagof(A,permutation(X,A),Y).  Try it online! -2 from steffan • you can use bagof instead of findall Sep 3, 2022 at 19:36 ## 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 Mar 6, 2012 at 17:03
• Why would using built-in language features be cheating? Mar 8, 2012 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(); } Mar 8, 2012 at 13:02

### 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)
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)
}else
t}
def hasNext=c!=s
def next={c+=1
g(c-1,l.toList)}
}
for(e<-new P("golf"))println(e)


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


# 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]}}  ## Python - 50 chars import itertools list(itertools.permutations("123"))  # 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=[] Mar 26, 2018 at 13:49 • Thanks ColdK. It worked and now is 8 bytes shorter. Mar 31, 2018 at 7:52 • Just saying, you can use ES6 arrow functions to knock off a few bytes – user100690 Mar 14, 2021 at 14:41 # 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. Oct 20, 2018 at 19:45 • Thank you! I can now shorten this to one byte! Oct 20, 2018 at 19:47 • This doesn't output unique permutations Apr 14, 2022 at 3:24 # Brachylog, 2 bytes pᵘ  Try it online!  ᵘ Find every unique p permutation of the input.  # Vyxal, 2 bytes ṖU  Try it Online! Ṗ # All permutations of input U # Filtered by unique  # JavaScript (ES6), 91 78 bytes -5 thanks to @Neil f=a=>a.length<2?[a]:a.flatMap((x,i)=>f(a.filter((_,j)=>i-j)).map(t=>[x,...t]))  Pretty normal recursive approach, and my first time using copyWithin :p Okay, copyWithin modifies the array, so that doesn't work. Used a different approach, which now saves more bytes. # Curry, 41 26 bytes 15 bytes saved by alephalpha Tested in PAKCS p[]=[] p(x++a:y)=a:p(x++y)  Try it online! Uses non-determinism to output all the permutations. This same code is used in my answer here for which I originally wrote it. • Shorter. Apr 8, 2022 at 8:58 # Knight, 180 bytes ;=i=jF;W=pP E++"=x"=i+1i" p";=s"";W>i-=j+1jT=s+++++++s";=y"j"F W>i-=y"j"+1y"j"T"E+s';=z=bF;W>i-=z+1zT;=aF W>i-=a+1aT|?z a=b|b?E+"y"zE+"y"a|b;=rF;=s"";W>z=r+1r=s++sE+"x"E+"y"r" "Os'  Try it online! This was a pain. Nested evals and stuff. Since recursion doesn't really work, I had to literally compose a string of nested while loops, and then eval it. Extremely inefficient, $$\O(n^{n+1})\$$ where $$\n\$$ is the length of the input. My browser started to freeze up with $$\n=6\$$. -2 bytes thanks to Aiden Chow. • You could combine =iF and =jF into =i=jF for -2 bytes. Aug 21, 2022 at 22:42 # 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, 2016 at 5:50 • 50 bytes Mar 14, 2021 at 18:48 # 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. Feb 26, 2018 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'
`