Zerlegen Sie eine Permutation in Zyklen

15

Es gibt einen bekannten Satz, dass jede Permutation in eine Reihe von Zyklen zerlegt werden kann . Ihre Aufgabe ist es, das kürzestmögliche Programm dafür zu schreiben.

Eingang:

Zwei Linien. Die erste enthält eine Zahl N, die zweite enthält Nverschiedene Ganzzahlen in dem [0,N-1]durch Leerzeichen getrennten Bereich . Diese Ganzzahlen repräsentieren eine Permutation von NElementen.

Ausgabe:

Eine Zeile für jeden Zyklus in der Permutation. Jede Zeile sollte eine durch Leerzeichen getrennte Liste von Ganzzahlen in Zyklusreihenfolge sein.

Zyklen können in beliebiger Reihenfolge ausgegeben werden, und jeder Zyklus kann von einer beliebigen Position aus ausgegeben werden.

Beispiel 1:

8
2 3 4 5 6 7 0 1

Dieser Eingang codiert die Permutation 0-> 2, 1-> 3, 2-> 4, 3-> 5, 4-> 6, 5-> 7, 6-> 0, 7-> 1. Dies zerfällt in Zyklen wie folgt:

0 2 4 6
1 3 5 7

Eine ebenso gültige Ausgabe wäre

5 7 1 3
2 4 6 0

Beispiel 2:

8
0 1 3 4 5 6 7 2

gültige Ausgabe:

0
1
4 5 6 7 2 3
code-golf math combinatorics permutations Keith Randall
quelle
@ Keith Was ist der Maximalwert von N?
17.
3
3 Zeichen in J:>C.
Eelvex
Sagen wir N <1000.
Keith Randall
Permutationen werden normalerweise von 1 aufwärts gezählt, nicht von 0.
Dr. belisarius
6
Mathematiker zählen von 1, Informatiker zählen von 0 :)
Keith Randall

Antworten:

4

C 145 134 Zeichen

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
quelle
Ist es legal, implizit deklarierte variadische Funktionen aufzurufen? Ist es legal, zuerst wegzulassen int?
6502
Es ist legal, alles zu tun, solange der Code funktioniert. Obwohl es möglicherweise Warnungen gibt, sollte es in Ordnung sein, solange es keine Fehler gibt.
20.
Der eigentliche Punkt liegt in der Bedeutung von "Werken". Auf jeden Fall habe ich eine Antwort (139 Zeichen) hinzugefügt , die verwendet diese Regel (dh wenn „Werke“ bedeutet „es gibt mindestens eine selbsterklärte C - Compiler , in dem offenbar die erzeugten Maschinencode Werke“)
6502
+1: Ich mag die gets(&i)Idee, diese nutzlose erste Zeile loszuwerden, aber dies würde auf 16-Bit-Systemen eindeutig nicht funktionieren, wenn mehr als 10 Elemente übergeben werden. Aber noch einmal, wenn die Regeln lauten, dass "mindestens ein Programm gefunden wird, das behauptet, ein C-Compiler zu sein, der eine ausführbare Datei erstellt, auf die in mindestens einem Fall - zumindest für mich - eine gültige Antwort zu geben scheint", dann ist dies eine Verbesserung: )
6502
2

Python 131 Zeichen

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

Die letzte Zeile wird nicht benötigt

6502
quelle
1

Haskell, 131 Zeichen

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) >=wurde >, eliminierte zwei tailAufrufe durch Pattern Matching & Pre-Application von a!!.
MtnViewMark
quelle
1

C (Art von), 139 Zeichen

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

Die letzte Zeile ist nicht enthalten.

Ich sagte "irgendwie", weil AFAIK zum Beispiel

  1. Es ist nicht legal, Deklaration für verschiedene Funktionen wegzulassen (ANSI C89: 3.3.2.2)
  2. intkann bei Variablendeklaration nicht weggelassen werden (Ich habe nicht gefunden, wo es heißt, dass es weggelassen werden kann, und die implizite Typdeklaration wird nur für Funktionen beschrieben. Die Grammatikspezifikation in der Norm ist im Grunde genommen nutzlos, da sie zum Beispiel viel mehr als gültige C-Deklarationen akzeptiert. double double void volatile x;)
  3. Eine neue Zeile am Ende einer nicht leeren Quelldatei ist obligatorisch (ANSI C89: A.6.2).

aber der obige mit kompilierte code gcc -ocycles cycles.cfunktioniert anscheinend trotzdem.

6502
quelle
Dies ist ein gültiges C-Programm, aber dies ist kein C99.
Quixotic
@ Debanjan: Nein, es ist nicht ANSI C (nicht einmal 89). Zum Beispiel besagt der Standard (3.3.2.2), dass eine Funktion, die eine variable Anzahl von Argumenten verwendet, nicht implizit an der Funktionsaufrufstelle deklariert werden kann (mit anderen Worten, Sie können nicht scanfohne einen Aufruf auskommen, #include <stdio.h>auch wenn die Parameter korrekt sind und keine Konvertierungen erfordern ):<<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 (zwischen 2 und 32)

Ich bin mir nicht ganz C.sicher , was das I / O-Format angeht, aber ich denke, es wäre gut, wenn die folgende Ausgabe akzeptiert würde:

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

(Im J-Terminal sieht es besser aus.)

Wenn es sich um eine benannte Funktion handeln muss, die meinem besten Verständnis des E / A-Formats entspricht, sind dies 32 Zeichen, von denen 30 für die Ausgabeformatkonvertierung bestimmt sind ...

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

In Aktion:

   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

Erläuterung:

J wird (praktisch) von rechts nach links ausgeführt. @ist eine 'Funktion' (technisch gesehen keine Funktion, aber das ist nah genug), um Funktionen zu kombinieren.

  • i.&LF- Ermitteln Sie den ersten Index LFeiner vordefinierten Variablen mit dem ASCII-Zeichen 10 und dem Zeilenvorschub.
  • >:- finde den ersten LFund erhöhe seinen Index um eins. Wir wollen eigentlich keinen Zeilenvorschub, wir wollen das Array, das darauf folgt.
  • }.~ - Wählt den gewünschten Teil der Eingabe aus.
  • ".- Da das Eingabeformat J ( * \ õ / * ) ist, können wir einfach das evalVerb (ich weiß, dass es nicht wirklich aufgerufen wird eval) verwenden, um es in ein Array zu verwandeln
  • C.- Pure Magie. Ich habe wirklich keine Ahnung, was das macht, aber es scheint zu funktionieren!
  • ":L:0- Vertretung. Wandelt die Ausgabe von C.in eine Folge von Strings um
  • >- Unbox. Die eigentliche Ausgabe ist eigentlich ein String-Array (es gibt Leerzeichen hinter den ersten bis zu den Zahlen des Beispiels).
ɐɔıɐɔuʇǝɥʇs
quelle
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"")))

Etwas ungolfed und in eine Funktion zerlegt (Eingabe muss ein Vektor sein, was (vec (wiederholt (lesen) lesen)) von oben ergibt):

(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, habe gerade bemerkt, dass diese Herausforderung über 3 Jahre alt ist. Na ja, es hat trotzdem Spaß gemacht!)

YosemiteMark
quelle