23
\$\begingroup\$

Consider a permutation of the integers 1, ..., n, such as this one for n = 6:

[5,2,4,3,6,1]

If you view the permutation as a mapping from [1,2,3,4,5,6] to [5,2,4,3,6,1], the permutation can be decomponsed into disjoint cycles. A cycle is a subset of elements that map to each other. For example, 1 gets mapped to 5, which gets mapped to 6, which gets mapped back to 1. So one cycle is [1,5,6]. The other cycles are [2] and [3,4]. Thus the number of cycles for this permutation is 3.

In general, the cycles of a permutation are unique (up to order), and the number of cycles for a permutation of size n varies from 1 to n.

The challenge

Given a non-empty permutation, output its number of cycles.

Input is an array formed by the n integers 1, 2, ..., n, where n > 0. Each integer occurs exactly once. The order in which they appear defines the permutation, as in the example above.

Instead of an array you can use a list, a string with a separator between the numbers, a separate input for each number, or anything that's reasonable.

For a permutation of size n, instead of the 1-based set of integers 1, ..., n you can consistently use the 0-based set 0, ..., n-1. If so, please indicate it in your answer.

The code should work for n up to 20 in a reasonable time, say less than one minute.

Code golf. All builtins allowed.

Test cases

This assumes 1-based, array input.

 [1] -> 1
 [3,2,1] -> 2
 [2,3,4,5,1] -> 1
 [5,2,4,3,6,1] -> 3
 [8,6,4,5,2,1,7,3] -> 2
 [4,5,11,12,7,1,3,9,10,6,8,2] -> 1
 [4,2,5,11,12,7,1,3,9,10,6,8] -> 5
 [5,8,6,18,16,9,14,10,11,12,4,20,15,19,2,17,1,13,7,3] -> 3
 [14,5,17,15,10,18,1,3,4,13,11,16,2,12,9,7,20,6,19,8] -> 7

Related

This related challenge asks for the actual cycles of the permutation, not the number of them. Requiring only the number of cycles can lead to shorter algorithms that sidestep generating the actual cycles.

\$\endgroup\$
  • \$\begingroup\$ Nevermind my question, it is stated in the question 0-based input is allowed. \$\endgroup\$ – orlp Aug 1 '16 at 23:44
  • \$\begingroup\$ @orlp That was quick! I didn't even get to see your question \$\endgroup\$ – Luis Mendo Aug 1 '16 at 23:50
  • \$\begingroup\$ Can we take a mapping of indexes to values as input? \$\endgroup\$ – Copper Aug 1 '16 at 23:59
  • 1
    \$\begingroup\$ @Copper I think yes, if the domain of the mapping is the set 1, ..., n in that order. Can you clarify how can a mapping be an input? Is it a data structure? \$\endgroup\$ – Luis Mendo Aug 2 '16 at 0:05
  • \$\begingroup\$ @LuisMendo Yes, it's a data structure, like a Python dict. I want to have {1: 2, 2: 1} as an input instead of [2, 1]. \$\endgroup\$ – Copper Aug 2 '16 at 0:07

12 Answers 12

12
\$\begingroup\$

J, 4 bytes

#@C.

This assumes that the permutation is 0-based. It uses the builtin C. which given a list representing a direct permutation outputs a list of cycles. Then # composed @ on that returns the number of cycles in that list.

Try it here.

\$\endgroup\$
  • 1
    \$\begingroup\$ That's cheating! :) \$\endgroup\$ – orlp Aug 1 '16 at 23:51
  • 1
    \$\begingroup\$ I should have banned builtins :-D \$\endgroup\$ – Luis Mendo Aug 1 '16 at 23:51
  • 2
    \$\begingroup\$ Builtins are love. Builtins are life. I do agree it would be more fun with builtins being banned. Feel free to change the rule right now before too many answer. \$\endgroup\$ – miles Aug 1 '16 at 23:54
  • \$\begingroup\$ @miles Nah, I'll leave it as it is. Good job! \$\endgroup\$ – Luis Mendo Aug 2 '16 at 0:18
7
\$\begingroup\$

JavaScript, 99 98 bytes

This solution assumes the array and its values are zero-indexed (e.g. [2, 1, 0]).

f=a=>{h={},i=c=0;while(i<a.length){s=i;while(!h[i]){h[i]=1;i=a[i]}c++;i=s;while(h[++i]);}return c}

Explanation

// assumes the array is valid and zero-indexed
var findCycles = (array) => {
    var hash = {};  // remembers visited nodes
    var index = 0;  // current node
    var count = 0;  // number of cycles
    var start;      // starting node of cycle

    // loop until all nodes visited
    while(index < array.length) {
        start = index;  // cache starting node

        // loop until found previously visited node
        while(!hash[index]) {
            hash[index] = 1;    // mark node as visited
            index = array[index];   // get next node
        }
        count++;    // increment number of cycles

        index = start + 1;  // assume next node is right after

        // loop until found unvisited node
        while(hash[index]) {
            index++;    // get next node
        }
    }

    return count;   // return number of cycles
};
\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to PPCG! Nice first answer! This is also one of the best, if not the best, first answer I have seen in my experience! Keep up the good work! \$\endgroup\$ – GamrCorps Aug 2 '16 at 6:19
  • \$\begingroup\$ Wow thank you so much! I actually had to look up how to do the lambdas in JavaScript. I'm not that familiar with the ES6 stuff yet. \$\endgroup\$ – kamoroso94 Aug 2 '16 at 8:27
6
\$\begingroup\$

Mathematica, 45 bytes

Length@ConnectedComponents@Thread[Sort@#->#]&

It generates a graph and counts its connected components.

\$\endgroup\$
6
\$\begingroup\$

Mathematica, 37 28 27 bytes

#~PermutationCycles~Length&

Thanks @alephalpha for saving 9 bytes, and @miles for 1 more byte.

\$\endgroup\$
  • 3
    \$\begingroup\$ PermutationCycles[#,Length]& \$\endgroup\$ – alephalpha Aug 2 '16 at 3:33
  • 3
    \$\begingroup\$ Oh that's neat. I didn't know PermutationCycles could take a second argument to alter the head of its output. You can also use infix notation to save another byte #~PermutationCycles~Length&. \$\endgroup\$ – miles Aug 2 '16 at 4:00
  • 1
    \$\begingroup\$ Also regarding your original solution, #& is a fair bit shorter than Identity. ;) \$\endgroup\$ – Martin Ender Aug 2 '16 at 8:05
6
\$\begingroup\$

Python, 77 69 67 bytes

f=lambda p,i=1:i and0 **p[i-1]+f(p[:i-1]+[0]+p[i:],p[i-1]or max(p))
\$\endgroup\$
  • \$\begingroup\$ (not p[i-1]) can be done as 0**p[i-1] \$\endgroup\$ – xnor Aug 2 '16 at 10:08
5
\$\begingroup\$

Jelly, 12 10 9 bytes

ị³$ÐĿ«/QL

Saved 1 byte thanks to @Dennis.

This uses 1-based permutations. It works by applying the permutation repeatedly until it reaches a previous permutation while also keeping its previous values. By keeping track of the changes, it will create the orbit for every value along the columns of that table. Then, by finding either the minimum or maximum of each column, a label for that cycle can be created. Then deduplicate that list of labels and get the length of it which will be the number of disjoint cycles.

Try it here.

Explanation

ị³$ÐĿ«/QL  Input: permutation p
  $        Chain (ị³) as a monad
 ³           The input p
ị            For each value x, get the value at index x in p
   ÐĿ      Invoke it on p initially, and repeat it on its next value until it returns
           to a previous value and keep track of the results
           This will create a table where each column is the orbit of each value
     «/    Get the minimum value along each column of that table
       Q   Deduplicate
        L  Get the length and return
\$\endgroup\$
  • \$\begingroup\$ Very nice approach! \$\endgroup\$ – Luis Mendo Aug 2 '16 at 0:53
  • \$\begingroup\$ ị³$ÐĿ«/QL should work. \$\endgroup\$ – Dennis Aug 2 '16 at 1:55
  • \$\begingroup\$ @Dennis Wow, that is a neat trick! Since each cycle is disjoint, taking either the max/min and using it as a label will be enough to deduplicate+length for the result. \$\endgroup\$ – miles Aug 2 '16 at 2:01
5
\$\begingroup\$

Python, 64 bytes

l=input()
for _ in l:l=[min(x,l[x])for x in l]
print len(set(l))

This golfed code happens to be idiomatic and readable. Uses 0-indexing.

Each value looks at what it points to and what the pointed value points to, and points to the smaller of the two. After enough repetitions, each element points to the smallest element of its cycle. The number of distinct elements pointed to is then the number of cycles.

It suffices to do n iterations. Alternatively, we could iterate until the list no longer changes. This strategy gave me a recursive function of the same length, 64 bytes:

f=lambda l,p=0:len(set(l*(l==p)))or f([min(x,l[x])for x in l],l)

Reducing was 65 bytes

lambda l:len(set(reduce(lambda l,_:[min(x,l[x])for x in l],l,l)))

The set(_) conversions can be shortened to {*_} in Python 3.5, saving 2 bytes.

\$\endgroup\$
4
\$\begingroup\$

Haskell, 111 bytes

l!i|l!!i<0=l|1<2=(take i l++[-1]++drop(i+1)l)!(l!!i)
f(x:y)|x>=0=0|1<2=1+f y
c l|l==[-1|x<-l]=0|1<2=1+c(l!f l)

Uses 0-based indexing

\$\endgroup\$
  • 4
    \$\begingroup\$ Damn, you better have a good programming font :) 1l!i|iIi!!1ll1| \$\endgroup\$ – orlp Aug 2 '16 at 1:02
  • \$\begingroup\$ @orlp and it's 111 bytes! :O \$\endgroup\$ – grooveplex Aug 2 '16 at 12:28
4
\$\begingroup\$

Pyth, 9 bytes

l{mS.u@QN

Uses 0-based indexes. Try it online.

How it works

  m         map for d in input:
    .u        cumulative fixed-point: starting at N=d, repeatedly replace N with
      @QN       input[N]
              until a duplicate is found, and return all intermediate results
   S          sort
 {          deduplicate
l           length
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 49 bytes

a=>a.reduce(g=(c,e,i)=>e<i?g(c,a[e],i):c+=e==i,0)

Uses zero-based indexing. Explanation: reduce is used to invoke the inner function g on each element of the array. c is the count of cycles, e is the array element, i is the array index. If the element is less than the index, then it's a potential cycle - the element is used to index into the array to find the next element in the cycle recursively. If we started out or end up with the original index then this is a new cycle and we increment the cycle count. If at any point we find a value larger than the index then we'll count that cycle later.

\$\endgroup\$
  • \$\begingroup\$ When I ran your code on the array [2,1,0,3,4,5], it crashed with this message "Maximum call stack size exceeded". \$\endgroup\$ – kamoroso94 Aug 2 '16 at 13:00
  • 1
    \$\begingroup\$ @kamoroso94 Sorry about that, a typo had crept in. Should be fixed now. \$\endgroup\$ – Neil Aug 2 '16 at 13:10
2
\$\begingroup\$

C, 90 bytes

Call f() with a mutable int array, 1 based indexing. The second parameter is the size of the array. The function returns the number of cycles.

i,j,c;f(a,n)int*a;{for(c=i=0;i<n;++i)for(j=0,c+=!!a[i];a[i];a[i]=0,i=j-1)j=a[i];return c;}

Try it on ideone.

The algorithm:

For each index
    If index is non-zero
        Increment counter
        Traverse the cycle, replacing each index in it with 0.
\$\endgroup\$
2
\$\begingroup\$

GAP, 30 bytes

Straightforward, the second argument to Cycles gives the set on which the permutation should act:

l->Size(Cycles(PermList(l),l))
\$\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.