Descomponer una permutación en ciclos.

15

Existe un teorema bien conocido de que cualquier permutación puede descomponerse en un conjunto de ciclos . Su trabajo es escribir el programa más corto posible para hacerlo.

Entrada:

Dos lineas. El primero contiene un número N, el segundo contiene Nenteros distintos en el rango [0,N-1]separados por espacios. Estos enteros representan una permutación de Nelementos.

Salida:

Una línea para cada ciclo en la permutación. Cada línea debe ser una lista de enteros separados por espacios en orden de ciclo.

Los ciclos se pueden generar en cualquier orden, y cada ciclo se puede generar comenzando en cualquier posición.

Ejemplo 1:

8
2 3 4 5 6 7 0 1

Esta entrada codifica la permutación 0-> 2, 1-> 3, 2-> 4, 3-> 5, 4-> 6, 5-> 7, 6-> 0, 7-> 1. Esto se descompone en ciclos como este:

0 2 4 6
1 3 5 7

Una salida igualmente válida sería

5 7 1 3
2 4 6 0

Ejemplo 2

8
0 1 3 4 5 6 7 2

salida válida:

0
1
4 5 6 7 2 3
Keith Randall
fuente
@Keith ¿Cuál es el valor máximo de N?
fR0DDY
3
3 caracteres en J:>C.
Eelvex
Digamos N <1000.
Keith Randall
Las permutaciones generalmente se cuentan desde 1, no 0.
Dr. belisarius
66
Los matemáticos cuentan desde 1, los informáticos cuentan desde 0 :)
Keith Randall

Respuestas:

4

C 145 134 Personajes

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

fR0DDY
fuente
¿Es legal llamar a funciones variadas declaradas implícitamente? ¿Es legal omitir primero int?
6502
Es legal hacer cualquier cosa mientras el código funcione. Si bien puede dar advertencias, siempre y cuando no dé errores, debería estar bien.
fR0DDY
El punto mismo está en el significado de "obras". De todos modos, he agregado una respuesta (139 caracteres) que usa esta regla (es decir, donde "funciona" significa "hay al menos un compilador de C autodeclarado en el que, aparentemente, el código de máquina generado funciona")
6502
+1: Me gusta la gets(&i)idea de deshacerme de esa primera línea inútil, sin embargo, esto claramente no funcionaría en sistemas de 16 bits si se pasan más de 10 elementos. Pero una vez más, si las reglas son "encontrar al menos un programa que dice ser un compilador de C que crea un ejecutable donde, al menos en un caso, parece, al menos para mí, dar una respuesta válida", entonces esta es una mejora: )
6502
2

Python 131 caracteres

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

la nueva línea final no es necesaria

6502
fuente
1

Haskell, 131 personajes

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
  • Editar: (135 -> 131) se >=convirtió >, eliminó dos tailllamadas a través de la coincidencia de patrones y la pre-aplicación de a!!.
MtnViewMark
fuente
1

C (más o menos), 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("");}}

La nueva línea final no está incluida.

Dije "algo así" porque AFAIK por ejemplo

  1. no es legal omitir la declaración de funciones variadas (ANSI C89: 3.3.2.2)
  2. int no se puede omitir para la declaración de variables (no encontré dónde se dice que se puede omitir y la declaración de tipo implícita solo se describe para funciones. La especificación gramatical en el estándar es básicamente inútil ya que acepta mucho más que declaraciones C válidas, por ejemplo double double void volatile x; )
  3. una nueva línea al final de un archivo fuente no vacío es obligatoria (ANSI C89: A.6.2)

pero el código anterior compilado gcc -ocycles cycles.caparentemente funciona de todos modos.

6502
fuente
Este es un programa C válido, pero no es C99.
Quijotesco
@Debanjan: No, no es ANSI C (ni siquiera 89). Por ejemplo, la norma dice (3.3.2.2) que si una función utiliza un número variable de argumentos, entonces no puede ser declarado implícitamente en el sitio de llamada de función (en otras palabras, no se puede llamar scanfsin #include <stdio.h>ni siquiera si los parámetros son correctos y no se requiere conversiones ):<<If the function is defined with a type that includes a prototype, and the types of the arguments after promotion are not compatible with the types of the parameters, or if the prototype ends with an ellipsis ( ", ..." ), the behavior is undefined.>>
6502
1

J (entre 2 y 32)

No tengo muy claro el formato de E / S, pero creo que C.lo haría si se aceptara la siguiente salida:

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

(Se ve mejor en la terminal J.)

Si necesita ser una función con nombre que cumpla con mi mejor comprensión del formato de E / S, serían 32 caracteres, de los cuales 30 son para la conversión del formato de salida ...

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

En acción:

   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

Explicación:

J se ejecuta de derecha a izquierda (prácticamente). @es una 'función' (técnicamente no es una función, pero está lo suficientemente cerca) para combinar funciones.

  • i.&LF- encuentre el primer índice de LF, una variable predefinida que contiene el número de caracteres ASCII 10, el avance de línea.
  • >:- encuentre el primero LFe incremente su índice en uno. En realidad no queremos el salto de línea, queremos la matriz que lo sigue.
  • }.~ - Selecciona la parte de la entrada que queremos.
  • ".- Dado que el formato de entrada es válido J ( * \ õ / * ) podemos usar el evalverbo (sé que en realidad no se llama eval) para convertirlo en una matriz
  • C.- Magia pura. Realmente no tengo idea de lo que hace, ¡pero parece funcionar!
  • ":L:0- Representación. Convierte la salida de C.en una secuencia de cadenas en caja
  • >- Unbox. El resultado real es en realidad una matriz de cadenas (hay espacios detrás del primero a los números del ejemplo).
ɐɔıʇǝɥʇuʎs
fuente
0

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

Algo sin golf y dividido en una función (la entrada debe ser un vector, que es lo que produce (vec (repetidamente (leer) leer)) desde arriba):

(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, acabo de notar que este desafío tiene más de 3 años. ¡Oh, bueno, me divertí haciéndolo de todos modos!)

YosemiteMark
fuente