I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com
get GPL
COST (GBP)
this unit 2.09
sub units 0.19
+
0

Partition

Computes the partition generated by the given permutation.
Controller: CodeCogs

get GPL add to cart

Dependents

Info

Interface

C++

Partition

 
std::vector<int>partitionintn
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:

then the vector v 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.