Partition

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:

then the vector $v$ would be

generating the following partition

Parameters

Returns

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