is_permutation

| Home | Libraries | People | FAQ | More

### is_permutation

The header file 'is_permutation.hpp' contains six variants of a single algorithm, `is_permutation`. The algorithm tests to see if one sequence is a permutation of a second one; in other words, it contains all the same members, possibly in a different order.

The routine `is_permutation` takes two sequences and an (optional) predicate. It returns true if the two sequences contain the same members. If it is passed a predicate, it uses the predicate to compare the elements of the sequence to see if they are the same.

`is_permutation` come in three forms. The first one takes two iterators to define the first range, and the starting iterator of the second range. The second form takes a two iterators to define the first range and two more to define the second range. The third form takes a single range parameter, and uses Boost.Range to traverse it.

##### Interface

The function `is_permutation` returns true if the two input sequences contain the same elements. There are six versions; two take three iterators, two take four iterators, and the other two take two ranges.

In general, you should prefer the four iterator versions over the three iterator ones. The three iterator version has to "create" the fourth iterator internally by calling `std::advance(first2, std::distance(first1,last1))`, and if the second sequence is shorter than the first, that's undefined behavior.

    template< class ForwardIterator1, class ForwardIterator2 >
    bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 );

    template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
    bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
                          ForwardIterator2 first2, BinaryPredicate p );

    template< class ForwardIterator1, class ForwardIterator2 >
    bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 );

    template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
    bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
                          ForwardIterator2 first2, ForwardIterator2 last2,
                          BinaryPredicate p );

    template <typename Range, typename ForwardIterator>
    bool is_permutation ( const Range &r, ForwardIterator first2 );

    template <typename Range, typename ForwardIterator, typename BinaryPredicate>
    bool is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred );

##### Examples

Given the container `c1` containing `{ 0, 1, 2, 3, 14, 15 }`, and `c2` containing `{ 15, 14, 3, 1, 2 }`, then

    is_permutation ( c1.begin(),     c1.end (), c2.begin(), c2.end ()) --> false
    is_permutation ( c1.begin() + 1, c1.end (), c2.begin(), c2.end ()) --> true

    is_permutation ( c1.end (), c1.end (), c2.end(), c2.end ()) --> true  // all empty ranges are permutations of each other

##### Iterator Requirements

`is_permutation` works on forward iterators or better.

##### Complexity

All of the variants of `is_permutation` run in O(N^2) (quadratic) time; that is, they compare against each element in the list (potentially) N times. If passed random-access iterators, `is_permutation` can return quickly if the sequences are different sizes.

##### Exception Safety

All of the variants of `is_permutation` take their parameters by value, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee.

##### Notes

- The three iterator versions of the routine `is_permutation` are part of the C++11 standard. When compiled using a C++11 implementation, the implementation from the standard library will be used.
- The four iterator versions of the routine `is_permutation` are part of the proposed C++14 standard. When C++14 standard libraries become available, the implementation should be changed to use the implementation from the standard library (if available).
- `is_permutation` returns true when passed a pair of empty ranges, no matter what predicate is passed to test with.