CodeCogs

Counts the number of cycles in a permutation.

Interface

#include <codecogs/maths/combinatorics/permutations/cycles.h>

using namespace Maths::Combinatorics::Permutations;

int cycles(int n, int *p)

Consider the permutation

$\sigma = \left( \begin{array}{cccc} 1 & 2 & \ldots & n \cr \sigma(1) & \sigma(2) & \ldots & \sigma(n) \end{array} \right)$

(1)

A <em> cycle </em> is a sequence of indices $i_1, i_2, \ldots, i_k$ such that

$i_p = \sigma(i_{p-1}), \qquad \forall p = \overline{2, k}$

(2)

and

$\sigma(i_k) = i_1$

(3)

This function calculates the number of cycles in a given permutation, using an efficient algorithm.

Example:

#include <codecogs/maths/combinatorics/permutations/cycles.h>
#include <iostream>
int main()
{
  int beta[9] = {2, 3, 9, 6, 7, 8, 5, 4, 1};
  std::cout << "The number of cycles of the Beta permutation: ";
  std::cout << Maths::Combinatorics::Permutations::cycles(9, beta);
  std::cout << std::endl;
  return 0;
}

Output:

The number of cycles of the Beta permutation: 3

References

SUBSET, a C++ library of combinatorial routines, http://www.csit.fsu.edu/~burkardt/cpp_src/subset/subset.html

Parameters

the size of the permutation

the actual permutation stored as an array

Returns

the number of cycles found in the permutation

Cycles