Number of cycles of a permutation

Question

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.

Answer 1

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.

Answer 2

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
};

Answer 3

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

Answer 4

Mathematica, 45 bytes

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

It generates a graph and counts its connected components.

Answer 5

Mathematica, 37 28 27 bytes

#~PermutationCycles~Length&

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

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

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

Answer 10

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.

Answer 11

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.

Answer 12

GAP, 30 bytes

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

l->Size(Cycles(PermList(l),l))