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

12 Answers 12

Reset to default
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

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Is it legal to call implicitly declared variadic functions? Is it legal to omit first int? \$\endgroup\$
    – 6502
    Commented Mar 19, 2011 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
    Commented Mar 20, 2011 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
    Commented Mar 20, 2011 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
    Commented Mar 22, 2011 at 7:30
3
\$\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

Improve this answer
\$\endgroup\$
2
\$\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).
Improve this answer
\$\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!!.
Improve this answer
\$\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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ This is a valid C program,but this is not C99. \$\endgroup\$
    – Quixotic
    Commented Mar 22, 2011 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
    Commented Mar 22, 2011 at 7:17
1
\$\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!)

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jelly, 17 bytes

ḲVJ’,Ɗy¥Ƭ`ZṢ€Q€QG

Try it online!

or with modern I/O standards, 14 bytes.

Takes N on STDIN and the list of numbers as the first command line argument

The last 5 bytes feel far too long for such a simple task

How it works

ḲVJ’,Ɗy¥Ƭ`ZṢ€Q€QG - Main link. Takes a string S on the left
Ḳ                 - Split S on spaces
 V                - Evaluate each element. Call this list of integer L
       ¥          - Group the previous 2 links into a dyad f(A, L):
     Ɗ            -   Group the previous 3 links into a monad g(A):
  J               -     Length range of A
   ’              -     Decrement to use 0 indexing
    ,             -     Pair with A
      y           -   Transliterate L using the mapping from g(A)
        Ƭ         - While results are unique, repeatedly apply f(A, L),
         `        -  starting with f(L, L)
          Z       - Transpose
           Ṣ€     - Sort each subarray
             Q€   - Deduplicate each subarray
               Q  - Deduplicate the whole array
                G - Join each subarray with spaces and the subarrays by newlines
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 110 bytes

(n,N=[])=>n.flatMap(e=>~N.indexOf(e)?[]:[(U=(T,P=T[T.length-1])=>N.push(P)&&(e==n[P]?T:U([...T,n[P]])))([e])])

Try it online!

This is the version which takes in a list of integers and outputs a 2d list, where each sublist is a cycle.

This version takes in the number of numbers (not used). The numbers are taken as a space-separated string, and the function returns a string formatted as described in the question. It is 141 bytes long.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 59 bytes

x=>x.flatMap(g=a=>1/x[a]?[[a,...g(x[a],x[a]=g)[0]||[]]]:[])

Try it online!

JavaScript (Node.js), 60 bytes

x=>x.flatMap(g=a=>[1/x[a]?[a,...g(x[a],delete x[a])[0]]:[]])

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 46 bytes

Needs["Combinatorica`"];Combinatorica`ToCycles

Complete code with test cases is:

Needs["Combinatorica`"];
Combinatorica`ToCycles /@ 
{
 {3, 4, 5, 6, 7, 8, 1, 2}, 
 {1, 2, 4, 5, 6, 7, 8, 3}, 
 {1, 2, 3}, 
 {1 , 2 , 4 , 5 , 6, 7 , 8, 3}
}
// Grid

$$ \left( \begin{array}{ccc} \{3,5,7,1\} & \{4,6,8,2\} & \text{Null} \\ \{1\} & \{2\} & \{4,5,6,7,8,3\} \\ \{1\} & \{2\} & \{3\} \\ \{1\} & \{2\} & \{4,5,6,7,8,3\} \\ \end{array} \right) $$

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Needs["Combinatorica`"] -> <<Combinatorica` \$\endgroup\$
    – alephalpha
    Commented Apr 3, 2023 at 7:12
0
\$\begingroup\$

Python3.8, 129 chars

def v(i):_=a[i];a[i]=-1;return~_ and[i]+v(_)or[]
input()
for i in range(len(a:=[*map(int,input().split())])):~a[i]and print(v(i))
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

MATL, 20 bytes

:wQy"yy)]v"@quS!]Xhu

Try it out!

Takes the liberty of assuming the second input is inside a pair of square brackets, but otherwise sticks to the requirements (spending 2 bytes on the 0-indexing for example). Works pretty similar to caird coinheringaahing's Jelly answer.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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