[Home]STLAlgorithmExtensions/InvertPermutation

BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List

Difference (from prior author revision) (major diff)

Changed: 2c2
sequence A into B, the permutation inverse(p) reorders B into A. Another words inverse(p)[p[i]] = i.
sequence A into B, the permutation inverse(p) reorders B into A. In other words inverse(p)[p[i]] = i.

The invert_permutation turns a permutation into the inverse permutation of itself. So given a permutation p that reorders sequence A into B, the permutation inverse(p) reorders B into A. In other words inverse(p)[p[i]] = i.

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;
}
The output is
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.


BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List
Edit text of this page | View other revisions
Last edited August 19, 2006 11:33 am (diff)
Search:
Disclaimer: This site not officially maintained by Boost Developers