Code-Golf: Permutacje


21

Napisz funkcję, która przyjmuje jako dane wejściowe zestaw liczb całkowitych (może to być lista, tablica lub dowolny inny kontener z odrębnymi liczbami) i wyświetla listę wszystkich jej permutacji.

Python (95 znaków) :

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

Byłoby miło być pobitym w tym samym języku, ale implementacje w innych językach są mile widziane!

Odpowiedzi:


10

Python - 76 znaków

Dłuższy niż gnibbler, ale wdraża rzeczy od zera.

p=lambda x:x and[[a]+b for a in x for b in p([c for c in x if c!=a])]or[[]]

Lubię tutaj rozumieć. To naprawdę upraszcza kod, który dużo opublikowałem!
zxul767


9

J, 11 znaków

(i.@!@#A.[)

Stosowanie:

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

Wyjaśnienie:

i.@!@# używa trzech czasowników, aby zwrócić listę od 0 do (! n) -1, gdzie n jest liczbą elementów na danej liście.

[zwraca samą listę. W pokazanym przykładzie to daje 0 1 2 3 4 5 A. 1 3 5.

A.zwraca jedną możliwą permutację drugiej listy dla każdego elementu na pierwszej liście (rodzaj - tutaj podano właściwe wyjaśnienie ).


Podaj link do informacji o J?
Sparr

1
@Sparr Na stronie J znajduje się kilka dobrych przewodników - nauka programistów J i J dla programistów C - oraz strona zawierająca słownictwo .
Gareth,

8

Python - 55 znaków

from itertools import*
p=lambda x:list(permutations(x))

Nie do końca to, co miałem nadzieję, że ludzie napiszą ... ale warto wiedzieć, że Python ma takie narzędzia w standardowej bibliotece.
zxul767

4
@ zxul767: Po co wymyślać koło ponownie? Korzystanie ze standardowej biblioteki okaże się niesamowicie wydajne ... (iw tym przypadku stanowi zwięzły kod podczas gry w golfa ;-)
ChristopheD

8

Haskell, 44 43

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

Zasadniczo to samo co rozwiązanie ugorena, ale Haskell jest lepszy w zrozumieniu list!


Oczywiście może to zrobić

30

import Data.List
p=permutations


Bardziej wydajne podejście, które nie wymaga porównania równości:

92

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

W konsekwencji ten działa również, gdy na liście znajdują się zduplikowane elementy.


4
Najlepsze jest to, że 44-liniowe rozwiązanie haskell ze zrozumieniem listy jest krótsze niż rozwiązanie python, które korzysta tylko ze standardowej biblioteki.
monadyczny

p=Data.List.permutations. Ale to jest oszustwo. Ponadto, Data.List.permutationsnie emituje permutacji w porządku leksykograficznym.
John Dvorak

1
Zamiast tego możesz pisać p[]=[[]]jako przypadek podstawowy, oszczędzając dwa bajty.
Lynn,

@Mauris: racja! W jakiś sposób założyłem, że pusta lista z definicji będzie miała zero permutacji, ale od 0! = 1, co wyraźnie nie ma sensu. Posiadanie pustej podstawy jest o wiele przyjemniejsze.
przestał się obracać przeciwnie do zegara

3

w Q (48)

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

Przykładowe użycie:

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

2

Rubin - 23 znaki

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

na przykład f[[1,2,3]] wypisuje to .

ale używanie [].permutationjest jak oszustwo, więc:

Ruby - 59 znaków

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

testowane z

100.times.all?{arr=(1..99).to_a.sample(rand(5)); arr.permutation.to_a==f[arr]}
=> true

Jeśli chcesz, możesz zademonstrować swój kod za pomocą strony takiej jak IdeOne: ideone.com/crvtD
Mr. Llama,

1
Dlaczego korzystanie z wbudowanych funkcji językowych byłoby oszustwem?
Mark Thomas

@Mark może nie oszukiwać, ale też nie jest zbyt zabawny, aby napisać funkcję wywołującą funkcję wbudowaną. Na przykład: „napisz funkcję do sortowania tablicy” ->f(array) { return array.sort(); }
jsvnm

2

Python - 58 znaków

Nieznacznie krótszy niż ugoren, biorąc zestaw jako dane wejściowe:

p=lambda x:x and[[y]+l for y in x for l in p(x-{y})]or[[]]

2

DO, 270 243 239 znaków

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

Funkcja P (n, a) zwraca wskaźnik do n! permutacje, zapakowane jeden po drugim w jedną gigantyczną tablicę.


1
Kilka wskazówek: rozmiar <malloc.h> isn't needed (ignore the warnings). n wynosi 4 (przenośność jest dobra, ale krótsza jest ładniejsza). Użyj dodatkowych parametrów jako zmiennych (np p(n,a,N,i).). int*p(..)int*a,o;. Korzystanie ze zmiennych globalnych zamiast parametrów i zwracanych wartości często pomaga.
ugoren,

@ugoren, dzięki za wskazówki. Do tej pory nie widziałem, jak golić kolejne postacie za pomocą globali. (I hej, ta funkcja jest bezpieczna dla wątków, jak jest!)
Michael Radford,


1

JS - 154 146 znaków

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')zwraca to .


1

R

Ponieważ mówimy o permutacjach, pozwól mi pokazać co najmniej jedno rozwiązanie w języku R:

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

1

Perl 188

Bez procedur bibliotecznych, bez rekurencji

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]}}

1

Scala 30:

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

Scala 195, quick'n'dirty, bez permutacji z biblioteki:

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, w pełni rozwinięty, bezpieczny iterator typu:

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)


1

Pyth, 4 bajty

L.pb

Tak, Pyth powstał po opublikowaniu tego wyzwania. To wciąż jest naprawdę fajne. :RE

Demo na żywo.

Odczyt ze standardowego wejścia jest krótszy o bajt:

.pQ

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>


Myślę, że możesz zyskać 8 bajtów, wykonując: js function p(s,a="",c="",i,z=[]){ zamiast js function p(s,a,c,i,z){if(!z)a=c="",z=[]
ColdK

Dzięki ColdK. Działa i teraz jest o 8 bajtów krótszy.
wolfhammer


0

Python, 53 bajty

from itertools import*;lambda x:list(permutations(x))

1
Jest to w zasadzie duplikat innej przesłanej odpowiedzi . Zakładam, że wymyśliłeś to samodzielnie (i lepiej grałeś w golfa), ale pomyślałem, że warto wskazać duplikat.


0

K (oK) , 3 bajty

Rozwiązanie

prm

Wypróbuj online!

Wyjaśnienie:

Jest to 3 bajt wbudowany skrót do dalszej wbudowane 47 funkcji bajtów:

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

... który można skrócić do 23 bajtów, jeśli wiemy, że otrzymujemy listę danych wejściowych jako danych wejściowych:

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

0

Aksjomat, 160 bajtów

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)

bez golfa

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

Wszystko to wywołuje jedną funkcję biblioteczną, która daje permutację na indeksie (tylko liczby całkowite jako permutacje jak permutacje na [1], permutacje na [1,2], permutacje na [1,2,3] itd.). indeksów i budować listy; Należy zauważyć, że wydaje się, że jest to dobrze skompilowane dla każdej listy typu 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

Czy masz link do tłumacza Axiom? Chciałbym go dodać do Try It Online! , wygląda na interesujący język.
caird coinheringaahing

0

Japt , 1 bajt

á

Japt interpreter

Zderzyło się to i nie otrzymałem odpowiedzi Japt, więc pomyślałem, że dodam jedną. ápo zastosowaniu do tablicy i bez żadnych argumentów wbudowane jest polecenie „pobierz wszystkie permutacje”. -RFlaga używana w linku interpretera tylko modyfikuje sposób wynik zostanie wydrukowany.


0

APL (NARS), 39 znaków, 78 bajtów

{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 

0

05AB1E - 2 1 bajty s

œ

Dane wejściowe muszą być tablicą / listą.

Wyjaśnienie:

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

Oszczędność bajtu dzięki Erikowi Outgolfer


Możesz traktować dane wejściowe jako pojedynczą listę, nie trzeba ich rozdzielać znakami nowej linii.
Erik the Outgolfer,

Dziękuję Ci! Teraz mogę skrócić to do jednego bajtu!
MilkyWay90,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.