Existe um teorema bem conhecido de que qualquer permutação pode ser decomposta em um conjunto de ciclos . Seu trabalho é escrever o programa mais curto possível para isso.

Entrada:

Duas linhas. O primeiro contém um número N, o segundo contém Nnúmeros inteiros distintos no intervalo, [0,N-1]separados por espaços. Esses números inteiros representam uma permutação de Nelementos.

Resultado:

Uma linha para cada ciclo na permutação. Cada linha deve ser uma lista separada por espaços de números inteiros em ordem de ciclo.

Os ciclos podem ser emitidos em qualquer ordem e cada ciclo pode ser iniciado a partir de qualquer posição.

Exemplo 1:

8
2 3 4 5 6 7 0 1

Esta entrada codifica a permutação 0-> 2, 1-> 3, 2-> 4, 3-> 5, 4-> 6, 5-> 7, 6-> 0, 7-> 1. Isso se decompõe em ciclos como este:

0 2 4 6
1 3 5 7

Uma saída igualmente válida seria

5 7 1 3
2 4 6 0

Exemplo 2:

8
0 1 3 4 5 6 7 2

saída válida:

0
1
4 5 6 7 2 3

C 145 134 caracteres

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

a nova linha final não é necessária

Haskell, 131 caracteres

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) >=tornou-se >, eliminou duas tailchamadas através de correspondência de padrões e pré-aplicação de a!!.

C (tipo de), 139 caracteres

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

A nova linha final não está incluída.

Eu disse "mais ou menos" porque o AFAIK, por exemplo

1. não é legal omitir a declaração para funções variadas (ANSI C89: 3.3.2.2)
2. intnão pode ser omitido para declaração de variável (não encontrei onde é dito que pode ser omitido e a declaração implícita de tipo é descrita apenas para funções. A especificação gramatical no padrão é basicamente inútil, pois aceita muito mais do que declarações C válidas, por exemplo double double void volatile x;)
3. uma nova linha no final de um arquivo de origem não vazio é obrigatória (ANSI C89: A.6.2)

mas o código acima compilado com gcc -ocycles cycles.caparentemente funciona de qualquer maneira.

J (entre 2 e 32)

Não sou muito claro quanto ao formato de E / S, mas acho que C.seria bom se a seguinte saída fosse aceita:

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

(Parece melhor no terminal J.)

Se precisar ser uma função nomeada que atenda ao meu melhor entendimento do formato de E / S, seriam 32 caracteres, dos quais 30 são para conversão de formato de saída ...

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

Em ação:

   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

Explicação:

J é executado da direita para a esquerda (praticamente). @é uma 'função' (não tecnicamente uma função, mas que é próxima o suficiente) para combinar funções.

• i.&LF- encontre o primeiro índice de LF, uma variável predefinida que contém o número de caracteres ASCII 10, o avanço de linha.
• >:- encontre o primeiro LFe aumente seu índice em um. Na verdade, não queremos o avanço de linha, queremos a matriz que o segue.
• }.~ - Seleciona a parte da entrada que queremos.
• ".- Como o formato de entrada é J ( * \ õ / * ) válido , podemos apenas usar o evalverbo (sei que na verdade não é chamado eval.) Para transformá-lo em uma matriz
• C.- Pura magia. Eu realmente não tenho idéia do que isso faz, mas parece funcionar!
• ":L:0- representação. Transforma a saída de C.em uma sequência de seqüências de caixa
• >- Unbox. A saída real é na verdade uma matriz de cadeias de caracteres (há espaços atrás do primeiro nos números do exemplo).

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

Um pouco não-destruído e dividido em uma função (a entrada deve ser um vetor, que é o que produz (vec (leitura repetida)) acima):

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

(Uau, acabei de perceber que esse desafio tem mais de 3 anos. Ah, bem, me diverti fazendo isso de qualquer maneira!)