Multiplication — Permutations

Computes the product of two permutations.

Interface

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

using namespace Maths::Combinatorics::Permutations;

std::vector<int> multiplication(int n, int *p1, int *p2)

If $\sigma$ and $\tau$ are permutations, given by

$$\sigma = \left( \begin{array}{cccc} 1 & 2 & \ldots & n \cr \sigma(1) & \sigma(2) & \ldots & \sigma(n) \end{array} \right)$$

(1)

and

$$\tau = \left( \begin{array}{cccc} 1 & 2 & \ldots & n \cr \tau(1) & \tau(2) & \ldots & \tau(n) \end{array} \right)$$

(2)

then the product $\sigma \circ \tau$ is calculated using the following formula

$$\sigma \circ \tau = \left( \begin{array}{cccc} 1 & 2 & \ldots & n \cr \sigma(\tau(1)) & \sigma(\tau(2)) & \ldots & \sigma(\tau(n)) \end{array} \right)$$

(3)

This function returns the result of the multiplication as a C++ vector object.

Parameters

the size of the permutations

the first permutation, sigma, given as an array (applied last, i.e. the outer function)

the second permutation, tau, given as an array (applied first, i.e. the inner function)

Returns

the product of the two permutations, stored as a C++ vector object

Example:

#include <codecogs/maths/combinatorics/permutations/multiplication.h>
#include <iostream>
int main()
{
  int sigma[5] = {5, 2, 1, 4, 3}, tau[5] = {3, 2, 5, 4, 1};
  std::vector<int> result = Maths::Combinatorics::Permutations::multiplication(5, sigma, tau);
  std::cout << "The multiplication of Sigma and Tau is: ";
  std::cout << std::endl;
  for (int i = 0; i < 5; i++)
    std::cout << result[i] << " ";
  std::cout << std::endl;
  std::cout << "This proves one is the inverse of the other.";
  std::cout << std::endl;
  return 0;
}

Output:

The multiplication of Sigma and Tau is:
1 2 3 4 5
This proves one is the inverse of the other.

References

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