# Permutation Iterator Adaptor

Defined in header boost/permutation_iterator.hpp

The permutation iterator adaptor provides an iterator to a permutation of a given range. (see definition of permutation). The adaptor takes two arguments

- an iterator to the range V on which the permutation will be applied
- the reindexing scheme that defines how the elements of V will be permuted.

Note that the permutation iterator is not limited to strict permutations of the given range V. The distance between begin and end of the reindexing iterators is allowed to be smaller compared to the size of the range V, in which case the permutation iterator only provides a permutation of a subrange of V. The indexes neither need to be unique. In this same context, it must be noted that the past the end permutation iterator is completely defined by means of the past-the-end iterator to the indices

## Synopsis

>     namespace boost {
>       template <class IndexIterator>
>       class permutation_iterator_policies;

>       template <class ElementIterator, class IndexIterator>
>       class permutation_iterator_generator;

>       template <class ElementIterator, class IndexIterator>
>       typename permutation_iterator_generator<ElementIterator, IndexIterator>::type
>       make_permutation_iterator(ElementIterator& base, IndexIterator& indexing);
>     }

## The Permutation Iterator Generator Class Template

The `permutation_iterator_generator` is a helper class whose purpose is to construct a permutation iterator type. This class has two template arguments, the first being the iterator type over the range V, the second being the type of the iterator over the indices.

>     template <class ElementIterator, class IndexIterator>
>     class permutation_iterator_generator
>     {
>     public:
>       typedef iterator_adaptor<...> type; // the resulting permutation iterator type
>     }

### Template Parameters

Parameter | Description
--- | ---
`ElementIterator` | The iterator over the elements to be permuted. This type must be a model of RandomAccessIterator
`IndexIterator` | The iterator over the new indexing scheme. This type must at least be a model of ForwardIterator. The `IndexIterator::value_type` must be convertible to the `ElementIterator::difference_type`.

### Concept Model

The permutation iterator is always a model of the same concept as the IndexIterator.

### Members

The permutation iterator implements the member functions and operators required for the Random Access Iterator concept. However, the permutation iterator can only meet the complexity guarantees of the same concept as the IndexIterator. Thus for instance, although the permutation iterator provides `operator+=(distance)`, this operation will take linear time in case the IndexIterator is a model of ForwardIterator instead of amortized constant time.

## The Permutation Iterator Object Generator

The `make_permutation_iterator()` function provides a convenient way to create permutation iterator objects. The function saves the user the trouble of explicitly writing out the iterator types.

>     template <class ElementIterator, class IndexIterator >
>     typename permutation_iterator_generator<ElementIterator, IndexIterator>::type
>     make_permutation_iterator(ElementIterator& base, IndexIterator& indices);

## Example

>       using namespace boost;
>       int i = 0;

>       typedef std::vector< int > element_range_type;
>       typedef std::list< int > index_type;

>       static const int element_range_size = 10;
>       static const int index_size = 4;

>       element_range_type elements( element_range_size );
>       for(element_range_type::iterator el_it = elements.begin() ; el_it != elements.end() ; ++el_it) *el_it = std::distance(elements.begin(), el_it);

>       index_type indices( index_size );
>       for(index_type::iterator i_it = indices.begin() ; i_it != indices.end() ; ++i_it ) *i_it = element_range_size - index_size + std::distance(indices.begin(), i_it);
>       std::reverse( indices.begin(), indices.end() );

>       typedef permutation_iterator_generator< element_range_type::iterator, index_type::iterator >::type permutation_type;
>       permutation_type begin = make_permutation_iterator( elements.begin(), indices.begin() );
>       permutation_type it = begin;
>       permutation_type end = make_permutation_iterator( elements.begin(), indices.end() );

>       std::cout << "The original range is : ";
>       std::copy( elements.begin(), elements.end(), std::ostream_iterator< int >( std::cout, " " ) );
>       std::cout << "\n";

>       std::cout << "The reindexing scheme is : ";
>       std::copy( indices.begin(), indices.end(), std::ostream_iterator< int >( std::cout, " " ) );
>       std::cout << "\n";

>       std::cout << "The permutated range is : ";
>       std::copy( begin, end, std::ostream_iterator< int >( std::cout, " " ) );
>       std::cout << "\n";

>       std::cout << "Elements at even indices in the permutation : ";
>       it = begin;
>       for(i = 0; i < index_size / 2 ; ++i, it+=2 ) std::cout << *it << " ";
>       std::cout << "\n";

>       std::cout << "Permutation backwards : ";
>       it = begin + (index_size);
>       assert( it != begin );
>       for( ; it-- != begin ; ) std::cout << *it << " ";
>       std::cout << "\n";

>       std::cout << "Iterate backward with stride 2 : ";
>       it = begin + (index_size - 1);
>       for(i = 0 ; i < index_size / 2 ; ++i, it-=2 ) std::cout << *it << " ";
>       std::cout << "\n";

Thanks: The permutation iterator is only a small addition to the superb iterator adaptors library of David Abrahams and Jeremy Siek.
Copyright 2001 Toon Knapen.