Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|improve this question

18 Answers 18

up vote 9 down vote accepted

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[[]]
share|improve this answer
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.[) 1 3 5
1 3 5
1 5 3
3 1 5
3 5 1
5 1 3
5 3 1


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

share|improve this answer
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))
share|improve this answer
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.

share|improve this answer

Haskell, 44 43

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


import Data.List

More efficient approach, that doesn't require an equality comparison:


import Data.List
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.

share|improve this answer
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
share|improve this answer

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


tested with

100.times.all?{arr=(1..99).to_a.sample(rand(5)); arr.permutation.to_a==f[arr]}
=> true
share|improve this answer
If you want, you can demo your code using a site like IdeOne: – 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
share|improve this answer

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.

share|improve this answer


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

share|improve this answer

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]}}
share|improve this answer

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)
def p(y:List[_])=(0 to(1 to y.size).product).foreach(z=>println(c(z,y)))

val y=List(0,1,2,3)

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)
def hasNext=c!=s
def next={c+=1
for(e<-new P("golf"))println(e)
share|improve this answer

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[[]]
share|improve this answer

C, 270 243 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.

share|improve this answer
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


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:

share|improve this answer

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
share|improve this answer
You have unnecessary whitespace. – lirtosiast Sep 13 '15 at 19:10

K, 30 bytes


No builtins!

share|improve this answer

JavaScript 143 136 134

function p(s,a,c,i,z){if(!z)a=c="",z=[]
return z}

var perms = p([1,2,3]);

document.getElementById('output').innerHTML = perms.join("\n");
<pre id="output"></pre>

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.