Cycles

Counts the number of cycles in a permutation.

Controller: CodeCogs

Contents

Interface
Cycles
Page Comments

Dependents

Interface

C++

Cycles

intcycles(	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)$

(2)

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

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

(3)

and

$\sigma(i_k) = i_1$

(4)

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

n	the size of the permutation
p	the actual permutation stored as an array

Returns

the number of cycles found in the permutation

Authors

Lucian Bentea (August 2005)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.