The invert_permutation turns a permutation into the inverse permutation for itself. So given a permutation p that reorders sequence A into B, the permutation inverse(p) reorders B into A. Another 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)
#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
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.