# 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