Decompose a permutation into cycles

Question

There is a well-known theorem that any permutation can be decomposed into a set of cycles. 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 1

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 2

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 3

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 4

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 5

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 6

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