STLAlgorithmExtensions/InvertPermutation

template <class PermIter>
void invert_permutation(PermIter X, PermIter Xend)

Example

#include <iostream>
#include <cassert>
#include <boost/graph/detail/permutation.hpp>

int main()
{
  char array[] = "abcde";
  std::cout << "original array: " << array << std::endl;
  int perm[] = { 1,3,2,4,0,5 };
  char permuted_array[6];
  boost::permute_copy(array, array + 6, perm, permuted_array);
  std::cout << "permuted array: " << permuted_array << std::endl;
  boost::invert_permutation(perm, perm + 6);
  boost::permute(permuted_array, permuted_array + 6, perm);
  std::cout << "original array: " << permuted_array << std::endl;  
  for (int i = 0; i < 5; ++i)
    assert(array[i] == permuted_array[i]);
  return EXIT_SUCCESS;
}

original array: abcde
permuted array: eacbd
original array: abcde

Implementation

The implementation can currently be found in a detail header of the Boost Graph Library [permutation.hpp]. It is based on the algorithm in Knuth Volume 1, page 176.