Breaks

Counts the number of breaks in a permutation.

Controller: CodeCogs

Contents

Interface
Break Count
Page Comments

Dependents

Interface

C++

Break Count

intbreak_count(	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> break </em> is a pair of neighbors whose values differ by more than 1, i.e.

$|\sigma(i) - \sigma(i+1)| \neq 1, \qquad i \in \{1, 2, \ldots, n - 1\}$

(3)

This function calculates the number of breaks in a permutation, using the following algorithm:

Starting with a permutation of order n.
We prepend an element labeled 0 and append an element labeled $\inline n + 1$ .
There are now $\inline n + 1$ pairs of neighbors.
We now search for indices $\inline i \in \{0, 1, 2, \ldots, n\}$ such that the above

inequality stands.

The identity permutation has a break count of 0. The maximum break count is $\inline n + 1$ .

Example:

#include <codecogs/maths/combinatorics/permutations/breaks.h>
#include <iostream>
int main()
{
  int sigma[5] = {2, 3, 4, 5, 1};
  std::cout << "The number of breaks of the Sigma permutation: ";
  std::cout << Maths::Combinatorics::Permutations::break_count(5, sigma);
  std::cout << std::endl;
  return 0;
}

Output:

The number of breaks of the Sigma 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 breaks 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.