Partition — Permutations

Computes the partition generated by the given permutation.

You're viewing an older version of this page (#5342). View the current version.

Interface

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

using namespace Maths::Combinatorics::Permutations;

std::vector<int> partition(int n, int *p)

The problem of finding the partition of the set $\{ 1, 2, \ldots, n \}$ generated by a certain permutation $\sigma$ is the same with finding its disjoint cycle decomposition. Therefore, each cycle would represent a subset of the original set. This function returns a C++ vector with the property that $v[i] = j$ if and only if $i$ belongs to the subset of order $j$. For instance, consider the following permutation:

$$\sigma = \left( \begin{array}{ccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \cr 2 & 3 & 9 & 6 & 7 & 8 & 5 & 4 & 1 \end{array} \right)$$

(1)

then the vector $v$ would be

$$v = (1, 1, 1, 2, 3, 2, 3, 2, 1)$$

(2)

generating the following partition

$$[9] = \{2, 3, 9, 1\} \cup \{6, 8, 4\} \cup \{7, 5\}$$

(3)

Parameters

the size of the permutation

the actual permutation given as an array

Returns

the partition generated by the given permutation, with the property stated in the documentation

Example:

#include <codecogs/maths/combinatorics/permutations/partition.h>
#include <iostream>
int main()
{
  int tau[9] = {2, 3, 9, 6, 7, 8, 5, 4, 1};
  std::vector<int> result = Maths::Combinatorics::Permutations::partition(9, tau);
  std::cout << "The partition of the [9] set induced by the Tau permutation is:";
  std::cout << std::endl;
  for (int i = 1; i <= 9; i++)
  {
    for (int j = 0; j < 9; j++)
      if (result[j] == i)
      {
        std::cout << "Subset " << i << " : { ";
        for (; j < 9; j++)
          if (result[j] == i)
            std::cout << tau[j] << " ";
        std::cout << "}" << std::endl;
      }
  }
  return 0;
}

Output:

The partition of the [9] set induced by the Tau permutation is:
Subset 1 : { 2 3 9 1 }
Subset 2 : { 6 8 4 }
Subset 3 : { 7 5 }

References

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