Rozkład permutację na cykle


15

Istnieje dobrze znane twierdzenie, że dowolną permutację można rozłożyć na zbiór cykli . Twoim zadaniem jest napisanie możliwie najkrótszego programu.

Wejście:

Dwie linie. Pierwszy zawiera liczbę N, drugi zawiera Nwyraźne liczby całkowite w zakresie [0,N-1]oddzielone spacjami. Te liczby całkowite reprezentują permutację Nelementów.

Wynik:

Jedna linia dla każdego cyklu w permutacji. Każdy wiersz powinien być oddzieloną spacjami listą liczb całkowitych w kolejności cyklicznej.

Cykle mogą być wyprowadzane w dowolnej kolejności, a każdy cykl może być generowany od dowolnej pozycji.

Przykład 1:

8
2 3 4 5 6 7 0 1

To wejście koduje permutację 0-> 2, 1-> 3, 2-> 4, 3-> 5, 4-> 6, 5-> 7, 6-> 0, 7-> 1. Rozkłada się to na takie cykle:

0 2 4 6
1 3 5 7

Równie poprawne wyjście byłoby

5 7 1 3
2 4 6 0

Przykład 2:

8
0 1 3 4 5 6 7 2

prawidłowe wyjście:

0
1
4 5 6 7 2 3

@Keith Jaka jest maksymalna wartość N?
fR0DDY 17.03.11

3
3 znaki w J:>C.
Eelvex

Powiedzmy, że N <1000.
Keith Randall

Permutacje zlicza się zwykle od 1, a nie 0.
Dr Belisarius

6
Matematycy liczą od 1, informatycy liczą od 0 :)
Keith Randall

Odpowiedzi:


4

C 145 134 znaków

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


Czy legalne jest wywoływanie niejawnie zadeklarowanych funkcji variadycznych? Czy najpierw można pominąć int?
6502

Dozwolone jest robienie czegokolwiek, dopóki kod działa. Chociaż może dawać ostrzeżenia, o ile nie powoduje błędów, powinno być OK.
fR0DDY

Sam punkt ma znaczenie „działa”. W każdym razie dodałem odpowiedź (139 znaków), która korzysta z tej reguły (tj. Gdzie „działa” oznacza „istnieje co najmniej jeden kompilator C z własnym zgłoszeniem, w którym najwyraźniej działa wygenerowany kod maszynowy”)
6502

+1: Podoba mi się gets(&i)pomysł, aby pozbyć się tej bezużytecznej pierwszej linii, jednak najwyraźniej nie działałoby to w systemach 16-bitowych, jeśli przejdzie więcej niż 10 elementów. Ale jeszcze raz, jeśli reguły „znajdują co najmniej program, który twierdzi, że jest kompilatorem C, który tworzy plik wykonywalny, w którym przynajmniej w jednym przypadku wydaje się - przynajmniej dla mnie - dać prawidłową odpowiedź”, to jest to poprawa: - )
6502

2

Python 131 znaków

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

końcowy znak nowej linii nie jest potrzebny


1

Haskell, 131 znaków

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
  • Edycja: (135 -> 131) >=stało się >, wyeliminowano dwa tailwywołania poprzez dopasowanie wzorca i wstępne zastosowanie a!!.

1

C (w pewnym sensie), 139 znaków

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

Ostateczna nowa linia nie jest uwzględniona.

Powiedziałem „sort-of”, bo na przykład AFAIK

  1. pomijanie deklaracji dla funkcji variadic jest niezgodne z prawem (ANSI C89: 3.3.2.2)
  2. int nie można pominąć w deklaracji zmiennej (nie znalazłem miejsca, w którym powiedziano, że można ją pominąć, a niejawna deklaracja typu jest opisana tylko dla funkcji. Specyfikacja gramatyki w standardzie jest w zasadzie bezużyteczna, ponieważ akceptuje na przykład znacznie więcej niż prawidłowe deklaracje C. double double void volatile x; )
  3. nowy wiersz na końcu niepustego pliku źródłowego jest obowiązkowy (ANSI C89: A.6.2)

ale powyższy kod skompilowany z gcc -ocycles cycles.cnajwyraźniej i tak działa.


Jest to poprawny program w języku C, ale nie jest to C99.
Kichot,

@Debanjan: Nie, to nie jest ANSI C (nawet 89). Na przykład standard mówi (3.3.2.2), że jeśli funkcja używa zmiennej liczby argumentów, nie można jej niejawnie zadeklarować w miejscu wywołania funkcji (innymi słowy, nie można wywoływać scanfbez, #include <stdio.h>nawet jeśli parametry są prawidłowe i nie wymagają konwersji ):<<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 (od 2 do 32)

Nie do końca rozumiem format we / wy, ale myślę, C.że tak, gdyby zaakceptowano następujące dane wyjściowe:

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

(Wygląda lepiej w terminalu J.)

Jeśli musi to być funkcja nazwana, która odpowiada mojemu najlepszemu zrozumieniu formatu we / wy, będzie to 32 znaki, z czego 30 to konwersja formatu wyjściowego ...

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

W akcji:

   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

Wyjaśnienie:

J jest wykonywany od prawej do lewej (praktycznie). @to „funkcja” (technicznie nie jest to funkcja, ale wystarczająco blisko) do łączenia funkcji.

  • i.&LF- znajdź pierwszy indeks LFpredefiniowanej zmiennej zawierającej znak ASCII o numerze 10, znak nowej linii.
  • >:- znajdź pierwszy LFi zwiększ jego indeks o jeden. W rzeczywistości nie chcemy podawania linii, chcemy tablicy, która za nią podąża.
  • }.~ - Wybiera tę część wejścia, którą chcemy.
  • ".- Ponieważ format wejściowy jest prawidłowy J ( * \ õ / * ), możemy po prostu użyć evalczasownika (wiem, że tak naprawdę nie jest wywoływany eval.), Aby przekształcić go w tablicę
  • C.- Czysta magia. Naprawdę nie mam pojęcia, co to działa, ale wydaje się, że działa!
  • ":L:0- reprezentacja. Zamienia dane wyjściowe C.w sekwencję ciągów w ramkach
  • >- Rozpakuj. Rzeczywistym wyjściem jest w rzeczywistości tablica ciągów (za pierwszymi liczbami w przykładzie znajdują się spacje).

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

Trochę niepoznany i podzielony na funkcję (wejście musi być wektorem, co jest tym, co (vec (wielokrotnie (czytaj) czytaj)) z powyższego):

(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, właśnie zauważyłem, że to wyzwanie ma ponad 3 lata. No cóż, i tak dobrze się bawiłem!)

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.