Breaks — Permutations

Counts the number of breaks in a permutation.

Interface

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

using namespace Maths::Combinatorics::Permutations;

int break_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)$$

(1)

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\}$$

(2)

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 $n + 1$.
There are now $n + 1$ pairs of neighbors.
We now search for indices $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 $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

the size of the permutation

the actual permutation stored as an array

Returns

the number of breaks found in the permutation