Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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

13 Answers 13

up vote 6 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
add comment

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
2  
@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
add comment

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

share|improve this answer
    
Provide a link to information about J? –  Sparr Nov 12 '12 at 23:00
1  
@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
add comment

Haskell, 44 43

p[n]=[[n]]
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[n]=[[n]]
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
2  
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 at 12:13
add comment

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
share|improve this answer
    
If you want, you can demo your code using a site like IdeOne: ideone.com/crvtD –  GigaWatt 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
add comment

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

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
1  
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
add comment

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

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

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

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

Python - 50 chars

import itertools
list(itertools.permutations("123"))
share|improve this answer
add comment

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

Your Answer

 
discard

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.