Code-Golf: Permutationen

21

Schreiben Sie eine Funktion, die eine Reihe von Ganzzahlen als Eingabe verwendet (dies kann eine Liste, ein Array oder ein beliebiger anderer Container mit unterschiedlichen Nummern sein), und geben Sie die Liste aller Permutationen aus.

Python (95 Zeichen) :

p=lambda s:s and sum(map(lambda e:map(lambda p:[e]+p,p(filter(lambda x:x!=e,s))),s),[]) or [[]]

Es wäre schön, in derselben Sprache geschlagen zu werden, aber Implementierungen in anderen Sprachen sind mehr als willkommen!

zxul767
quelle

Antworten:

10

Python - 76 Zeichen

Länger als bei Gnibbler, implementiert aber Dinge von Grund auf neu.

p=lambda x:x and[[a]+b for a in x for b in p([c for c in x if c!=a])]or[[]]
ugoren
quelle
Ich mag die Verwendung von Verständnis hier. Es vereinfacht wirklich den Code, den ich viel gepostet habe!
zxul767
9

J, 11 Zeichen

(i.@!@#A.[)

Verwendung:

   (i.@!@#A.[) 1 3 5
1 3 5
1 5 3
3 1 5
3 5 1
5 1 3
5 3 1

Erläuterung:

i.@!@# verwendet drei Verben, um eine Liste von 0 bis (! n) -1 zurückzugeben, wobei n die Anzahl der Elemente in der angegebenen Liste ist.

[gibt die Liste selbst zurück. In dem gezeigten Beispiel gibt das 0 1 2 3 4 5 A. 1 3 5.

A.gibt eine mögliche Permutation der zweiten Liste für jedes Element in der ersten Liste zurück (Art von - die richtige Erklärung finden Sie hier ).

Gareth
quelle
Geben Sie einen Link zu Informationen über J?
Sparr,
1
@Sparr Auf der J-Website finden Sie einige gute Anleitungen - Lernen von J und J für C-Programmierer - sowie eine Seite mit dem Wortschatz .
Gareth,
8

Python - 55 Zeichen

from itertools import*
p=lambda x:list(permutations(x))
Knabberzeug
quelle
Nicht genau das, was ich mir erhofft hatte, aber es ist nützlich zu wissen, dass Python solche Dienstprogramme in der Standardbibliothek hat.
zxul767
4
@ zxul767: Warum das Rad neu erfinden? Die Verwendung der Standardbibliothek wird sich als unglaublich effizient erweisen ... (und sorgt in diesem Fall für einen präzisen Code beim Golfen ;-)
ChristopheD
8

Haskell, 44 43

p[]=[[]]
p l=[e:r|e<-l,r<-p$filter(/=e)l]

Im Wesentlichen das Gleiche wie die Lösung von ugoren, aber Haskell ist besser darin, Listen zu verstehen!


Natürlich kann es auch

30

import Data.List
p=permutations


Effizienterer Ansatz, der keinen Gleichstellungsvergleich erfordert:

92

import Data.List
p[]=[[]]
p l=(\(l,(e:r))->map(e:)$p(l++r))=<<(init$zip(inits l)(tails l))

Aus diesem Grund funktioniert dies auch, wenn die Liste doppelte Elemente enthält.

hörte auf, sich gegen den Uhrzeigersinn zu drehen
quelle
4
Das Beste daran ist, dass die 44-Zeilen-Haskell-Lösung mit dem Listenverständnis kürzer ist als die Python-Lösung, die nur die Standardbibliothek verwendet.
Monade
p=Data.List.permutations. Es fühlt sich an, als würde man schummeln. Auch Data.List.permutationsnicht ausgibt , die Permutationen in lexikographische Ordnung.
John Dvorak
1
Sie können p[]=[[]]stattdessen als Basisfall schreiben und dabei zwei Bytes sparen.
Lynn
@ Mauris: richtig! Ich habe irgendwie angenommen, dass die leere Liste per Definition null Permutationen haben würde, aber seit 0! = 1 das ergibt offensichtlich keinen Sinn. Ein leerer Koffer ist viel schöner.
aufgehört, sich
3

in Q (48)

g:{$[x=1;y;raze .z.s[x-1;y]{x,/:y except x}\:y]}

Beispielnutzung:

q)g[3;1 2 3]
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
sinedcm
quelle
2

Rubin - 23 Zeichen

f=->x{p *x.permutation}

beispielsweise f[[1,2,3]] gibt diese .

aber mit [].permutationfühlt sich an wie Betrug, so:

Rubin - 59 Zeichen

f=->a{a.size<2?[a]:a.flat_map{|x|f[(a-x=[x])].map{|y|x+y}}}

getestet mit

100.times.all?{arr=(1..99).to_a.sample(rand(5)); arr.permutation.to_a==f[arr]}
=> true
jsvnm
quelle
Wenn Sie möchten, können Sie Ihren Code auf einer Website wie IdeOne testen: ideone.com/crvtD
Mr. Llama
1
Warum sollten eingebaute Sprachfunktionen betrügen?
Mark Thomas
@Mark schummelt vielleicht nicht, macht aber auch nicht viel Spaß, eine Funktion zu schreiben, die nur eine eingebaute Funktion aufruft. Wie zum Beispiel: "Schreiben Sie eine Funktion, um ein Array zu sortieren" ->f(array) { return array.sort(); }
jsvnm
2

Python - 58 Zeichen

Etwas kürzer als bei Ugoren, wenn man einen Satz als Eingabe nimmt:

p=lambda x:x and[[y]+l for y in x for l in p(x-{y})]or[[]]
Jules Olléon
quelle
2

C, 270 243 239 Zeichen

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

Die Funktion P (n, a) liefert einen Zeiger auf das n! Permutationen von a, nacheinander in einem riesigen Array gepackt.

Michael Radford
quelle
1
Einige Tipps: <malloc.h> isn't needed (ignore the warnings). sizeof n` ist 4 (Portabilität ist schön, aber kürzer ist schöner). Verwenden Sie zusätzliche Parameter als Variablen (z p(n,a,N,i). B. ). int*p(..)int*a,o;. Oft hilft es, globale Variablen anstelle von Parametern und Rückgabewerten zu verwenden.
Ugoren
@ugoren, danke für die Tipps. Bisher habe ich noch nicht gesehen, wie ich weitere Charaktere mit Globals rasieren kann. (Und hey, die Funktion ist so wie sie ist threadsicher!)
Michael Radford
2

K, 30 Bytes

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

Keine eingebauten!

kirbyfan64sos
quelle
1

JS - 154 146 Zeichen

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')gibt dies zurück .

JiminP
quelle
1

R

Da es sich um Permutationen handelt, lassen Sie mich mindestens eine Lösung in R zeigen:

library(gtools);v=c(3,4,5);permutations(length(v),length(v),v)
Paolo
quelle
1

Perl 188

Keine Bibliotheksroutinen, keine Rekursion

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]}}
seltsam
quelle
1

Scala 30:

def p(s:Seq[_])=s.permutations 

Scala 195, quick'n'dirty, ohne Permutationen aus der Bibliothek:

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, ausgewachsen, typsicherer 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)
Benutzer unbekannt
quelle
1

Python - 50 Zeichen

import itertools
list(itertools.permutations("123"))
Jared Burrows
quelle
Warum sollte dies 5 Jahre später abgelehnt werden?
Jared Burrows
1

Pyth, 4 Bytes

L.pb

Ja, Pyth wurde erstellt, nachdem diese Herausforderung veröffentlicht wurde. Das ist immer noch sehr cool. : D

Live-Demo.

Das Lesen von stdin ist ein Byte kürzer:

.pQ
kirbyfan64sos
quelle
1

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>

Wolfhammer
quelle
Ich denke, Sie könnten 8 Bytes gewinnen, indem Sie js function p(s,a="",c="",i,z=[]){js function p(s,a,c,i,z){if(!z)a=c="",z=[]
Folgendes
Vielen Dank ColdK. Es hat funktioniert und ist jetzt 8 Bytes kürzer.
Wolfhammer
0

Python, 53 Bytes

from itertools import*;lambda x:list(permutations(x))
Oliver Ni
quelle
1
Dies ist im Grunde ein Duplikat einer anderen eingereichten Antwort . Ich nehme an, Sie haben es unabhängig erfunden (und Sie haben es besser gespielt), aber ich dachte, es lohnt sich, auf das Duplikat hinzuweisen.
0

K (oK) , 3 Bytes

Lösung

prm

Probieren Sie es online!

Erläuterung:

Es handelt sich um eine integrierte 3-Byte - Verknüpfung zu der folgenden integrierten 47-Byte-Funktion:

{[x]{[x]$[x;,/x ,''o'x ^/:x;,x]}@$[-8>@x;!x;x]}

... der auf 23 Bytes verkürzt werden kann, wenn wir wissen, dass wir eine Liste von Ints als Eingabe erhalten:

{$[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)
Streetster
quelle
0

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 dies ruft eine Bibliotheksfunktion auf, die die Permutation für den Index angibt (nur Ganzzahlen als Permutation wie Permutationen für [1], Permutationen für [1,2], Permutationen für [1,2,3] usw.) von Indizes und bauen die Listen; Man muss beachten, dass dies für jede Liste vom Typ X gut zu kompilieren scheint

(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
RosLuP
quelle
Haben Sie einen Link zum Axiom-Interpreter? Ich würde es gerne zu Try It Online hinzufügen lassen ! Es sieht aus wie eine interessante Sprache.
Caird Coinheringaahing
0

Japt , 1 Byte

á

Japt-Dolmetscher

Dies wurde gestoßen und hatte keine Antwort von Japt, also dachte ich, ich würde weitermachen und eine hinzufügen. áWenn es auf ein Array angewendet wird und keine Argumente enthält, ist das eingebaute Element für "alle Permutationen abrufen". Das -Rim Interpreter-Link verwendete Flag ändert nur, wie das Ergebnis gedruckt wird.

Kamil Drakari
quelle
0

APL (NARS), 39 Zeichen, 78 Byte

{1≥k←≢w←,⍵:⊂w⋄↑,/{w[⍵],¨q w[a∼⍵]}¨a←⍳k}

Prüfung:

  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 
RosLuP
quelle
0

05AB1E - 2 1 Byte s

œ

Die Eingabe muss ein Array / eine Liste sein.

Erläuterung:

œ //Takes all the permutations of the elements in the top of the stack (the input is a list, so it would work)

Dank Erik the Outgolfer ein Byte gespart

MilkyWay90
quelle
Sie können Eingaben als einzelne Liste annehmen, ohne sie durch Zeilenumbrüche trennen zu müssen.
Erik the Outgolfer
Vielen Dank! Ich kann das jetzt auf ein Byte kürzen!
MilkyWay90