20
\$\begingroup\$

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!

\$\endgroup\$

25 Answers 25

10
\$\begingroup\$

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[[]]
\$\endgroup\$
  • \$\begingroup\$ I like the usage of comprehensions here. It really simplifies the code I posted a lot! \$\endgroup\$ – zxul767 Mar 6 '12 at 9:09
16
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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

\$\endgroup\$
8
\$\begingroup\$

Python - 55 chars

from itertools import*
p=lambda x:list(permutations(x))
\$\endgroup\$
  • \$\begingroup\$ Not exactly what I was hoping folks would write... but it's useful to know Python has such utilities in the standard library. \$\endgroup\$ – zxul767 Mar 6 '12 at 9:15
  • 4
    \$\begingroup\$ @zxul767: Why reinvent the wheel? Using the standard library will prove incredibly efficient... (and in this case makes for concise code when golfing ;-) \$\endgroup\$ – ChristopheD Mar 6 '12 at 15:19
8
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – monadic Mar 30 '12 at 0:32
  • \$\begingroup\$ p=Data.List.permutations. It feels like cheating, though. Also, Data.List.permutations doesn't output the permutations in lexicographic order. \$\endgroup\$ – John Dvorak Apr 9 '14 at 12:13
  • 1
    \$\begingroup\$ You can write p[]=[[]] as a base case instead, saving two bytes. \$\endgroup\$ – Lynn Sep 10 '15 at 6:55
  • \$\begingroup\$ @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. \$\endgroup\$ – ceased to turn counterclockwis Sep 10 '15 at 10:54
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ If you want, you can demo your code using a site like IdeOne: ideone.com/crvtD \$\endgroup\$ – Mr. Llama Mar 6 '12 at 17:03
  • 1
    \$\begingroup\$ Why would using built-in language features be cheating? \$\endgroup\$ – Mark Thomas Mar 8 '12 at 0:46
  • \$\begingroup\$ @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(); } \$\endgroup\$ – jsvnm Mar 8 '12 at 13:02
2
\$\begingroup\$

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[[]]
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – ugoren Nov 12 '12 at 21:48
  • \$\begingroup\$ @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!) \$\endgroup\$ – Michael Radford Nov 13 '12 at 22:51
2
\$\begingroup\$

K, 30 bytes

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

No builtins!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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]}}
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

Python - 50 chars

import itertools
list(itertools.permutations("123"))
\$\endgroup\$
  • \$\begingroup\$ Why would this be downvoted 5 years later? \$\endgroup\$ – Jared Burrows Nov 10 '17 at 21:15
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 2 bytes

pᵘ

Try it online!

 ᵘ    Find every unique
p     permutation of the input.
\$\endgroup\$
0
\$\begingroup\$

Python, 53 bytes

from itertools import*;lambda x:list(permutations(x))
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – user62131 Nov 23 '16 at 5:50
0
\$\begingroup\$

Jelly, 2 bytes

Œ!

Try it online!

Yay for builtins!

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – caird coinheringaahing Feb 26 '18 at 20:18
0
\$\begingroup\$

JavaScript 143 136 134 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>

\$\endgroup\$
  • \$\begingroup\$ 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=[] \$\endgroup\$ – ColdK Mar 26 '18 at 13:49
  • \$\begingroup\$ Thanks ColdK. It worked and now is 8 bytes shorter. \$\endgroup\$ – wolfhammer Mar 31 '18 at 7:52
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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 
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You can take input as a single list, no need to take it separated by newlines. \$\endgroup\$ – Erik the Outgolfer Oct 20 '18 at 19:45
  • \$\begingroup\$ Thank you! I can now shorten this to one byte! \$\endgroup\$ – MilkyWay90 Oct 20 '18 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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