Istnieje dobrze znane twierdzenie, że dowolną permutację można rozłożyć na zbiór cykli . Twoim zadaniem jest napisanie możliwie najkrótszego programu.

Wejście:

Dwie linie. Pierwszy zawiera liczbę N, drugi zawiera Nwyraźne liczby całkowite w zakresie [0,N-1]oddzielone spacjami. Te liczby całkowite reprezentują permutację Nelementów.

Wynik:

Jedna linia dla każdego cyklu w permutacji. Każdy wiersz powinien być oddzieloną spacjami listą liczb całkowitych w kolejności cyklicznej.

Cykle mogą być wyprowadzane w dowolnej kolejności, a każdy cykl może być generowany od dowolnej pozycji.

Przykład 1:

8
2 3 4 5 6 7 0 1

To wejście koduje permutację 0-> 2, 1-> 3, 2-> 4, 3-> 5, 4-> 6, 5-> 7, 6-> 0, 7-> 1. Rozkłada się to na takie cykle:

0 2 4 6
1 3 5 7

Równie poprawne wyjście byłoby

5 7 1 3
2 4 6 0

Przykład 2:

8
0 1 3 4 5 6 7 2

prawidłowe wyjście:

0
1
4 5 6 7 2 3

C 145 134 znaków

N,A[999],i,j,f;main(){gets(&i);for(;~scanf("%d",A+N);)N++;for(;j<N;j++,f=f&&!puts(""))while(i=A[j]+1)f=printf("%d ",j),A[j]=-1,j=--i;}

http://www.ideone.com/BrWJT

Python 131 znaków

input();d=dict((i,int(x))for i,x in enumerate(raw_input().split()))
while d:
 x=list(d)[0]
 while x in d:print x,;x=d.pop(x)
 print

końcowy znak nowej linii nie jest potrzebny

Haskell, 131 znaków

n%l|all(>n)l=(n:l>>=(++" ").show)++"\n"|1<3=""
c(_:a)=a>>=(\n->n%(takeWhile(/=n)$iterate(a!!)$a!!n))
main=interact$c.map read.words

• Edycja: (135 -> 131) >=stało się >, wyeliminowano dwa tailwywołania poprzez dopasowanie wzorca i wstępne zastosowanie a!!.

C (w pewnym sensie), 139 znaków

n,j,t,a[999];main(){scanf("%*i");for(;scanf("%i",a+n)>0;)n++;while(n--)if(a[j=n]+1){for(;t=a[j]+1;a[j]=-1,j=t)printf("%i ",--t);puts("");}}

Ostateczna nowa linia nie jest uwzględniona.

Powiedziałem „sort-of”, bo na przykład AFAIK

1. pomijanie deklaracji dla funkcji variadic jest niezgodne z prawem (ANSI C89: 3.3.2.2)
2. int nie można pominąć w deklaracji zmiennej (nie znalazłem miejsca, w którym powiedziano, że można ją pominąć, a niejawna deklaracja typu jest opisana tylko dla funkcji. Specyfikacja gramatyki w standardzie jest w zasadzie bezużyteczna, ponieważ akceptuje na przykład znacznie więcej niż prawidłowe deklaracje C. double double void volatile x; )
3. nowy wiersz na końcu niepustego pliku źródłowego jest obowiązkowy (ANSI C89: A.6.2)

ale powyższy kod skompilowany z gcc -ocycles cycles.cnajwyraźniej i tak działa.

J (od 2 do 32)

Nie do końca rozumiem format we / wy, ale myślę, C.że tak, gdyby zaakceptowano następujące dane wyjściowe:

   C. 0 1 3 4 5 6 7 2
┌─┬─┬───────────┐
│0│1│7 2 3 4 5 6│
└─┴─┴───────────┘

(Wygląda lepiej w terminalu J.)

Jeśli musi to być funkcja nazwana, która odpowiada mojemu najlepszemu zrozumieniu formatu we / wy, będzie to 32 znaki, z czego 30 to konwersja formatu wyjściowego ...

g=:>@(":L:0)@(C.@".@}.~>:@i.&LF)

W akcji:

   g=:>@(":L:0)@(C.@".@}.~>:@i.&LF)
   g
>@(":L:0)@(C.@".@}.~ >:@i.&(10{a.))
   t
8
0 1 3 4 5 6 7 2
   g t
0          
1          
7 2 3 4 5 6

Wyjaśnienie:

J jest wykonywany od prawej do lewej (praktycznie). @to „funkcja” (technicznie nie jest to funkcja, ale wystarczająco blisko) do łączenia funkcji.

• i.&LF- znajdź pierwszy indeks LFpredefiniowanej zmiennej zawierającej znak ASCII o numerze 10, znak nowej linii.
• >:- znajdź pierwszy LFi zwiększ jego indeks o jeden. W rzeczywistości nie chcemy podawania linii, chcemy tablicy, która za nią podąża.
• }.~ - Wybiera tę część wejścia, którą chcemy.
• ".- Ponieważ format wejściowy jest prawidłowy J ( * \ õ / * ), możemy po prostu użyć evalczasownika (wiem, że tak naprawdę nie jest wywoływany eval.), Aby przekształcić go w tablicę
• C.- Czysta magia. Naprawdę nie mam pojęcia, co to działa, ale wydaje się, że działa!
• ":L:0- reprezentacja. Zamienia dane wyjściowe C.w sekwencję ciągów w ramkach
• >- Rozpakuj. Rzeczywistym wyjściem jest w rzeczywistości tablica ciągów (za pierwszymi liczbami w przykładzie znajdują się spacje).

Clojure, 145

(let[v(vec(repeatedly(read)read))](loop[a(set v)b 0](cond(a(v b))(do(print" "b)(recur(disj a(v b))(v b)))(seq a)(do(prn)(recur a(first a)))1"")))

Trochę niepoznany i podzielony na funkcję (wejście musi być wektorem, co jest tym, co (vec (wielokrotnie (czytaj) czytaj)) z powyższego):

(defn p [v]
  (loop [a (set v) b 0]
    (cond
     (a (v b)) (do (print" "b) (recur (disj a (v b)) (v b)))
     (seq a) (do (prn) (recur a (first a)))
     1 "")))

(Wow, właśnie zauważyłem, że to wyzwanie ma ponad 3 lata. No cóż, i tak dobrze się bawiłem!)