# 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

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

-
Provide a link to information about J? – Sparr Nov 12 '12 at 23:00
@Sparr The J website has a couple of good guides - Learning J and J for C programmers - and a page covering the vocabulary. – Gareth Nov 13 '12 at 9:03

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

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

-

``````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. – Jan 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 - 50 chars

``````import itertools
list(itertools.permutations("123"))
``````
-

## 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)
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[[]]
``````
-

# 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

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

# Scala (1 tweet)

``````def ps[A](l: List[A]): List[List[A]] = l match {
case _ :: Nil => List(l)
case _ => for {a <- l; p <- ps(l diff List(a))} yield a :: p
}
``````
-
You have unnecessary whitespace. – lirtosiast Sep 13 '15 at 19:10

# K, 30 bytes

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

No builtins!

-

# JavaScript 143136 134

``````function p(s,a,c,i,z){if(!z)a=c="",z=[]
a+=c,i=s.length
if(!i)z.push(a)
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>``

-