23
\$\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\$
0

32 Answers 32

17
\$\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\$
1
  • \$\begingroup\$ I've submitted a golfing suggestion to this answer which makes it shorter than your answer. \$\endgroup\$ Mar 14, 2021 at 18:50
11
\$\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\$
1
  • \$\begingroup\$ I like the usage of comprehensions here. It really simplifies the code I posted a lot! \$\endgroup\$
    – zxul767
    Mar 6, 2012 at 9:09
10
\$\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\$
2
8
\$\begingroup\$

Python - 55 chars

from itertools import*
p=lambda x:list(permutations(x))
\$\endgroup\$
2
  • \$\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, 2012 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\$ Mar 6, 2012 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
  • 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, 2012 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\$ Apr 9, 2014 at 12:13
  • 1
    \$\begingroup\$ You can write p[]=[[]] as a base case instead, saving two bytes. \$\endgroup\$
    – Lynn
    Sep 10, 2015 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\$ Sep 10, 2015 at 10:54
4
\$\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\$
4
  • 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, 2012 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\$ Nov 13, 2012 at 22:51
  • \$\begingroup\$ 215 bytes \$\endgroup\$
    – c--
    Aug 17, 2022 at 20:42
  • \$\begingroup\$ 181 bytes \$\endgroup\$
    – vengy
    Mar 21 at 1:39
4
+100
\$\begingroup\$

Prolog (SWI), 33 bytes

X-Y:-bagof(A,permutation(X,A),Y).

Try it online!

-2 from steffan

\$\endgroup\$
1
  • \$\begingroup\$ you can use bagof instead of findall \$\endgroup\$
    – naffetS
    Sep 3, 2022 at 19:36
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\$
0
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\$
3
  • \$\begingroup\$ If you want, you can demo your code using a site like IdeOne: ideone.com/crvtD \$\endgroup\$
    – Mr. Llama
    Mar 6, 2012 at 17:03
  • 1
    \$\begingroup\$ Why would using built-in language features be cheating? \$\endgroup\$ Mar 8, 2012 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, 2012 at 13:02
2
\$\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\$
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\$

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\$

Python - 50 chars

import itertools
list(itertools.permutations("123"))
\$\endgroup\$
0
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\$

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\$
3
  • \$\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, 2018 at 13:49
  • \$\begingroup\$ Thanks ColdK. It worked and now is 8 bytes shorter. \$\endgroup\$
    – wolfhammer
    Mar 31, 2018 at 7:52
  • \$\begingroup\$ Just saying, you can use ES6 arrow functions to knock off a few bytes \$\endgroup\$
    – user100690
    Mar 14, 2021 at 14:41
1
\$\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\$
3
1
\$\begingroup\$

Brachylog, 2 bytes

pᵘ

Try it online!

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

Vyxal, 2 bytes

ṖU

Try it Online!

Ṗ  # All permutations of input 
 U # Filtered by unique
\$\endgroup\$
1
\$\begingroup\$

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.

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

Curry, 41 26 bytes

15 bytes saved by alephalpha

Tested in PAKCS

p[]=[]
p(x++a:y)=a:p(x++y)

Try it online!

Uses non-determinism to output all the permutations. This same code is used in my answer here for which I originally wrote it.

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

Knight, 180 bytes

;=i=jF;W=pP E++"=x"=i+1i" p";=s"";W>i-=j+1jT=s+++++++s";=y"j"F W>i-=y"j"+1y"j"T"E+s';=z=bF;W>i-=z+1zT;=aF W>i-=a+1aT|?z a=b|b?E+"y"zE+"y"a|b;=rF;=s"";W>z=r+1r=s++sE+"x"E+"y"r" "Os'

Try it online!

This was a pain. Nested evals and stuff. Since recursion doesn't really work, I had to literally compose a string of nested while loops, and then eval it. Extremely inefficient, \$O(n^{n+1})\$ where \$n\$ is the length of the input. My browser started to freeze up with \$n=6\$.

-2 bytes thanks to Aiden Chow.

\$\endgroup\$
1
  • \$\begingroup\$ You could combine =iF and =jF into =i=jF for -2 bytes. \$\endgroup\$
    – Aiden Chow
    Aug 21, 2022 at 22:42
1
\$\begingroup\$

K (ngn/k), 15 bytes

{x@?<'+!a#a:#x}

Try it online!

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

Perl 5, 66 bytes

sub{$"=",";grep{my%t;@t{@$_}++;@_==%t}map{[/\d+/g]}glob"{@_}-"x@_}

Try it online!

Relies on the problem definition of distinct integers. Also horribly wasteful--it creates n**n candidates only to discard the ones that duplicate members within them.

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

Python, 53 bytes

from itertools import*;lambda x:list(permutations(x))
\$\endgroup\$
2
  • 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, 2016 at 5:50
  • 1
    \$\begingroup\$ 50 bytes \$\endgroup\$ Mar 14, 2021 at 18:48
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\$
1
  • \$\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\$ Feb 26, 2018 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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