[Question]
  [
There is a well-known theorem that [any permutation can be decomposed into a set of cycles](http://en.wikipedia.org/wiki/Permutation#Notation). Your job is to write the shortest possible program to do so.
## Input:
Two lines. The first contains a number `N`, the second contains `N` distinct integers in the range `[0,N-1]` separated by spaces. These integers represent a permutation of `N` elements.
## Output:
One line for each cycle in the permutation. Each line should be a space-separated list of integers in cycle order.
Cycles can be output in any order, and each cycle can be output starting at any position.
## Example 1:
```
8
2 3 4 5 6 7 0 1
```
This input encodes the permutation 0->2, 1->3, 2->4, 3->5, 4->6, 5->7, 6->0, 7->1. This decomposes into cycles like this:
```
0 2 4 6
1 3 5 7
```
An equally valid output would be
```
5 7 1 3
2 4 6 0
```
## Example 2:
```
8
0 1 3 4 5 6 7 2
```
valid output:
```
0
1
4 5 6 7 2 3
```
  
[Answer]
**C ~~145~~ 134 Characters**
```
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>
[Answer]
# Python 131 chars
```
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
```
the ending newline is not needed
[Answer]
# J (between 2 and 32)
I'm not quite clear on i/o format, but I think `C.` would do, if the following output would be accepted:
```
   C. 0 1 3 4 5 6 7 2
┌─┬─┬───────────┐
│0│1│7 2 3 4 5 6│
└─┴─┴───────────┘
```
(It looks better in the J terminal.)
If it needs to be a named function that complies to my best understanding of the i/o format, that'd be 32 characters, of which 30 are for output format conversion...
```
g=:>@(":L:0)@(C.@".@}.~>:@i.&LF)
```
In action:
```
   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
```
## Explanation:
J is executed from right to left (practically). `@` is a 'function' (not technically a function, but that's close enough) to combine functions.
* `i.&LF` - find the first index of `LF`, a predefined variable
containing ASCII character number 10, the line feed.
* `>:` - find the first `LF`, and increment it's index by one. We don't actually want the linefeed, we want the array that follows it.
* `}.~` - Selects the part of the input that we want.
* `".` - Since the input format is valid J (*\*\õ/\**) we can just use the `eval` verb (I know it's not actually called `eval`.) to turn it into an array
* `C.` - Pure magic. I really have no idea what this does, but it seems to work!
* `":L:0` - Representation. Turns the output of `C.` into a boxed sequence of strings
* `>` - Unbox. The actual output is actually a string array (there are spaces behind the first to numbers of the example).
[Answer]
## Haskell, 131 characters
```
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
```
* Edit: (135 -> 131) `>=` became `>`, eliminated two `tail` calls though pattern matching & pre-application of `a!!`.
[Answer]
# C (sort of), 139 chars
```
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("");}}
```
The final newline is not included.
I said "sort-of" because AFAIK for example
1. it's not legal to omit declaration for variadic functions (ANSI C89: 3.3.2.2)
2. `int` cannot be omitted for variable declaration (I didn't find where it's said it can be omitted and implicit type declaration is only described for functions. The grammar specification in the standard is basically useless as accepts much more than valid C declarations, for example `double double void volatile x;`)
3. a newline at the end of a non-empty source file is mandatory (ANSI C89: A.6.2)
but the above code compiled with `gcc -ocycles cycles.c` apparently works anyway.
[Answer]
# 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"")))
```
Somewhat ungolfed, and broken out into a function (input must be a vector, which is what (vec(repeatedly(read)read)) from above produces):
```
(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, just noticed this challenge is over 3 year old. Oh well, had fun doing it anyways!)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 17 bytes
```
ḲVJ’,Ɗy¥Ƭ`ZṢ€Q€QG
```
[Try it online!](https://tio.run/##y0rNyan8///hjk1hXo8aZuoc66o8tPTYmoSohzsXPWpaEwjC7v//W/w3UjBWMFEwVTBTMFcwUDAEAA "Jelly – Try It Online")
or with modern I/O standards, [14 bytes](https://tio.run/##y0rNyan8/9/rUcNMnWNdlYeWHluTEPVw56JHTWsCQfj/4fajkx7unKEZ@f9/tJGOgrGOgomOgqmOgpmOgrmOgoGOgmGsjkI0iMaQNIoFAA).
Takes `N` on STDIN and the list of numbers as the first command line argument
The last 5 bytes feel far too long for such a simple task
## How it works
```
ḲVJ’,Ɗy¥Ƭ`ZṢ€Q€QG - Main link. Takes a string S on the left
Ḳ                 - Split S on spaces
 V                - Evaluate each element. Call this list of integer L
       ¥          - Group the previous 2 links into a dyad f(A, L):
     Ɗ            -   Group the previous 3 links into a monad g(A):
  J               -     Length range of A
   ’              -     Decrement to use 0 indexing
    ,             -     Pair with A
      y           -   Transliterate L using the mapping from g(A)
        Ƭ         - While results are unique, repeatedly apply f(A, L),
         `        -  starting with f(L, L)
          Z       - Transpose
           Ṣ€     - Sort each subarray
             Q€   - Deduplicate each subarray
               Q  - Deduplicate the whole array
                G - Join each subarray with spaces and the subarrays by newlines
```
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 110 bytes
```
(n,N=[])=>n.flatMap(e=>~N.indexOf(e)?[]:[(U=(T,P=T[T.length-1])=>N.push(P)&&(e==n[P]?T:U([...T,n[P]])))([e])])
```
[Try it online!](https://tio.run/##dYy9CoMwFEb3PojcC9fQ2j8Qok9Q6xCnkEE0UUtIpNrSqa@e6lYKHb/DOd@tftZTcx/GOXa@1cHwAI4KLhXyzDFj6/lSj6B59i7Y4Fr9uhrQmEuVSqg4CCq5kIJZ7bq5j3drVrDxMfVQYhQtIXeyVLlIK5CMMUHrVIgIUitUGBrvJm81s74DAzKhPR3oSCc605aWP9z8GAv9cpI/xsrDBw "JavaScript (Node.js) – Try It Online")
This is the version which takes in a list of integers and outputs a 2d list, where each sublist is a cycle.
[This version](https://tio.run/##jc2/CsIwEMfx3adwkjs4D/8rQvQJrB3iFIINNdVKSIqt4uSr16qDdXO7H3w/3NncTJle8qLq@3CwdSZq2JMhLwyXhcurpJtQJJRGsfKcOVNtTAFWrB4R5/5g79sMLK6VXirYCZAUC6kkO@uP1ak/fLGIi2t5ghh7vQYKr2K9lssdKGaW9JoaEUFZjZrPIffNS/wcnaROgy@Ds@zCETJYkBrRmCY0pRnNaUDDL8FOu/1db9nULTv6V44/st3XTw) takes in the number of numbers (not used). The numbers are taken as a space-separated string, and the function returns a string formatted as described in the question. It is 141 bytes long.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 59 bytes
```
x=>x.flatMap(g=a=>1/x[a]?[[a,...g(x[a],x[a]=g)[0]||[]]]:[])
```
[Try it online!](https://tio.run/##y0osSyxOLsosKNHNy09J/Z9m@7/C1q5CLy0nscQ3sUAj3TbR1s5QvyI6MdY@OjpRR09PL10DxNMBEbbpmtEGsTU10bGxsVbRsZr/k/PzivNzUvVy8tM10jSijXSMdUx0THXMdMx1DHQMYzU1udBUAEWR1BjhUAES/w8A "JavaScript (Node.js) – Try It Online")
# [JavaScript (Node.js)](https://nodejs.org), 60 bytes
```
x=>x.flatMap(g=a=>[1/x[a]?[a,...g(x[a],delete x[a])[0]]:[]])
```
[Try it online!](https://tio.run/##dcpNCsIwEIbhvadwmcAY2/pTEFJP4AmGWQztJCihKTZIbh/NTgR33/fyPPjF6/i8L2k3x0mKsyXbIRsXON14Ud6yHbDdZ2S6IoMxxqt6YJIgSbZ1a2yILkikyxjnNQYxIXrlFHZwgCOc4Aw9NNCS1psf8alfpvsjai9v "JavaScript (Node.js) – Try It Online")
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 46 bytes
```
Needs["Combinatorica`"];Combinatorica`ToCycles
```
Complete code with test cases is:
```
Needs["Combinatorica`"];
Combinatorica`ToCycles /@ 
{
 {3, 4, 5, 6, 7, 8, 1, 2}, 
 {1, 2, 4, 5, 6, 7, 8, 3}, 
 {1, 2, 3}, 
 {1 , 2 , 4 , 5 , 6, 7 , 8, 3}
}
// Grid
```
$$
\left(
\begin{array}{ccc}
 \{3,5,7,1\} & \{4,6,8,2\} & \text{Null} \\
 \{1\} & \{2\} & \{4,5,6,7,8,3\} \\
 \{1\} & \{2\} & \{3\} \\
 \{1\} & \{2\} & \{4,5,6,7,8,3\} \\
\end{array}
\right)
$$
[Answer]
Python3.8, 129 chars
```
def v(i):_=a[i];a[i]=-1;return~_ and[i]+v(_)or[]
input()
for i in range(len(a:=[*map(int,input().split())])):~a[i]and print(v(i))
```
[Answer]
# MATL, 20 bytes
```
:wQy"yy)]v"@quS!]Xhu
```
[Try it out!](https://matl.suever.net/?code=%3AwQy%22yy%29%5Dv%22%40quS%21%5DXhu&inputs=8%0A%5B2+3+4+5+6+7+0+1%5D&version=22.4.0)
Takes the liberty of assuming the second input is inside a pair of square brackets, but otherwise sticks to the requirements (spending 2 bytes on the 0-indexing for example). Works pretty similar to caird coinheringaahing's Jelly answer.
]