Ada teorema terkenal bahwa permutasi apa pun dapat diuraikan menjadi satu set siklus . Tugas Anda adalah menulis program sesingkat mungkin untuk melakukannya.

Memasukkan:

Dua baris. Yang pertama berisi angka N, yang kedua berisi Nbilangan bulat yang berbeda dalam rentang yang [0,N-1]dipisahkan oleh spasi. Bilangan bulat ini mewakili permutasi Nelemen.

Keluaran:

Satu baris untuk setiap siklus dalam permutasi. Setiap baris harus berupa daftar bilangan bulat yang dipisahkan spasi dalam urutan siklus.

Siklus dapat berupa output dalam urutan apa pun, dan setiap siklus dapat berupa output yang dimulai dari posisi mana pun.

Contoh 1:

8
2 3 4 5 6 7 0 1

Input ini mengkodekan permutasi 0-> 2, 1-> 3, 2-> 4, 3-> 5, 4-> 6, 5-> 7, 6-> 0, 7-> 1. Ini terurai menjadi siklus seperti ini:

0 2 4 6
1 3 5 7

Output yang sama validnya adalah

5 7 1 3
2 4 6 0

Contoh 2:

8
0 1 3 4 5 6 7 2

output yang valid:

0
1
4 5 6 7 2 3

C 145 134 Karakter

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 karakter

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

baris akhir yang berakhir tidak diperlukan

Haskell, 131 karakter

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

• Sunting: (135 -> 131) >=menjadi >, menghilangkan dua tailpanggilan melalui pencocokan pola & pra-aplikasi a!!.

C (semacam), 139 karakter

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("");}}

Baris baru terakhir tidak termasuk.

Saya mengatakan "semacam" karena AFAIK misalnya

1. itu tidak sah untuk menghilangkan deklarasi untuk fungsi variadic (ANSI C89: 3.3.2.2)
2. int tidak dapat dihilangkan untuk deklarasi variabel (saya tidak menemukan di mana dikatakan itu dapat dihilangkan dan deklarasi tipe implisit hanya dijelaskan untuk fungsi. Spesifikasi tata bahasa pada standar pada dasarnya tidak berguna karena menerima lebih dari deklarasi C yang valid, misalnya double double void volatile x; )
3. baris baru di akhir file sumber tidak-kosong adalah wajib (ANSI C89: A.6.2)

tetapi kode di atas yang dikompilasi gcc -ocycles cycles.cternyata bekerja dengan baik.

J (antara 2 dan 32)

Saya tidak begitu jelas tentang format i / o, tapi saya pikir C.akan lakukan, jika output berikut akan diterima:

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

(Terlihat lebih baik di terminal J.)

Jika perlu fungsi bernama yang sesuai dengan pemahaman terbaik saya tentang format i / o, itu akan menjadi 32 karakter, 30 di antaranya untuk konversi format output ...

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

Beraksi:

   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

Penjelasan:

J dieksekusi dari kanan ke kiri (praktis). @adalah 'fungsi' (tidak secara teknis fungsi, tapi itu cukup dekat) untuk menggabungkan fungsi.

• i.&LF- cari indeks pertama LF, variabel yang sudah ditentukan yang berisi nomor karakter ASCII 10, umpan baris.
• >:- temukan yang pertama LF, dan tambahkan indeksnya satu per satu. Kami sebenarnya tidak ingin linefeed, kami ingin array yang mengikutinya.
• }.~ - Memilih bagian dari input yang kita inginkan.
• ".- Karena format input adalah J yang benar ( * \ õ / * ) kita hanya bisa menggunakan evalkata kerja (saya tahu itu tidak benar-benar disebuteval .) Untuk mengubahnya menjadi array
• C.- Sihir murni. Saya benar-benar tidak tahu apa ini, tetapi tampaknya berhasil!
• ":L:0- Representasi. Mengubah output dariC. menjadi urutan string kotak
• >- Buka kotak. Output aktual sebenarnya adalah array string (ada spasi di belakang yang pertama ke nomor contoh).

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

Agak tidak terubah, dan pecah menjadi fungsi (input harus berupa vektor, yaitu apa (vec (berulang kali (baca) baca)) dari hasil di atas):

(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, baru perhatikan tantangan ini sudah lebih dari 3 tahun. Oh well, bersenang-senang melakukannya!)