15
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ @Keith What is the maximum value of N? \$\endgroup\$ – fR0DDY Mar 17 '11 at 17:34
  • 3
    \$\begingroup\$ 3 chars in J :>C. \$\endgroup\$ – Eelvex Mar 17 '11 at 18:07
  • \$\begingroup\$ Let's say N<1000. \$\endgroup\$ – Keith Randall Mar 17 '11 at 18:14
  • \$\begingroup\$ Permutations are usually counted up from 1, not 0. \$\endgroup\$ – Dr. belisarius Mar 18 '11 at 16:23
  • 6
    \$\begingroup\$ Mathematicians count from 1, computer scientists count from 0 :) \$\endgroup\$ – Keith Randall Mar 18 '11 at 23:45
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Is it legal to call implicitly declared variadic functions? Is it legal to omit first int? \$\endgroup\$ – 6502 Mar 19 '11 at 23:13
  • \$\begingroup\$ It is legal to do anything as long as the code works. While it may give warnings, as long as it does not give errors, it should be Ok. \$\endgroup\$ – fR0DDY Mar 20 '11 at 3:45
  • \$\begingroup\$ The very point is in the meaning of "works". Anyway I've added an answer (139 chars) that uses this rule (i.e. where "works" means "there is at least one self-declared C compiler in which, apparently, the generated machine code works") \$\endgroup\$ – 6502 Mar 20 '11 at 8:15
  • \$\begingroup\$ +1: I like the gets(&i) idea to get rid of that useless first line, however this clearly wouldn't work on 16-bit systems if more than 10 elements are passed. But once again if the rules are "finding at least a program that claims to be a C compiler that creates an executable where in at least one case seems - at least to me - to give a valid response" then this is an improvement :-) \$\endgroup\$ – 6502 Mar 22 '11 at 7:30
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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!!.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This is a valid C program,but this is not C99. \$\endgroup\$ – Quixotic Mar 22 '11 at 1:06
  • \$\begingroup\$ @Debanjan: No it's not ANSI C (not even 89). For example the standard says (3.3.2.2) that if a function uses a variable number of arguments then it cannot be declared implicitly at the function call site (in other words you cannot call scanf without #include <stdio.h> even if the parameters are correct and do not require conversions): <<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.>> \$\endgroup\$ – 6502 Mar 22 '11 at 7:17
1
\$\begingroup\$

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).
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.