# 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 '21 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 '12 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 '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 ;-) Mar 6 '12 at 15:19

## Haskell, 44 43

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 '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. 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. 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 Mar 6 '12 at 17:03
• Why would using built-in language features be cheating? 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(); } 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. 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!) 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[0],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? 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=[] Mar 26 '18 at 13:49 • Thanks ColdK. It worked and now is 8 bytes shorter. Mar 31 '18 at 7:52 • Just saying, you can use ES6 arrow functions to knock off a few bytes – user100690 Mar 14 '21 at 14:41 # Brachylog, 2 bytes pᵘ  Try it online!  ᵘ Find every unique p permutation of the input.  # 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. # 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 • 50 bytes Mar 14 '21 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 [1], 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 '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'
abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba


# 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 '18 at 19:45
• Thank you! I can now shorten this to one byte! Oct 20 '18 at 19:47

# Vyxal, 2 bytes

ṖU


Try it Online!

Ṗ  # All permutations of input
U # Filtered by unique
`