Partition

Dependents

this module uses 1 subunits Check

Interface

Partition

The problem of finding the partition of the set generated by a certain permutation 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 if and only if belongs to the subset of order . For instance, consider the following permutation:

then the vector would be

generating the following partition

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

Returns

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

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.