Namespaces
Variants

std:: is_permutation

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
is_permutation
(C++11)


C library
Numeric operations
Operations on uninitialized memory
Definiert im Header <algorithm>
template < class ForwardIt1, class ForwardIt2 >

bool is_permutation ( ForwardIt1 first1, ForwardIt1 last1,

ForwardIt2 first2 ) ;
(1) (seit C++11)
(constexpr seit C++20)
template < class ForwardIt1, class ForwardIt2,

class BinaryPredicate >
bool is_permutation ( ForwardIt1 first1, ForwardIt1 last1,

ForwardIt2 first2, BinaryPredicate p ) ;
(2) (seit C++11)
(constexpr seit C++20)
template < class ForwardIt1, class ForwardIt2 >

bool is_permutation ( ForwardIt1 first1, ForwardIt1 last1,

ForwardIt2 first2, ForwardIt2 last2 ) ;
(3) (seit C++14)
(constexpr seit C++20)
template < class ForwardIt1, class ForwardIt2,

class BinaryPredicate >
bool is_permutation ( ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2,

BinaryPredicate p ) ;
(4) (seit C++14)
(constexpr seit C++20)

Überprüft, ob [ first1 , last1 ) eine Permutation eines Bereichs ist, der bei first2 beginnt:

  • Für Überladungen (1,2) hat der zweite Bereich std:: distance ( first1, last1 ) Elemente.
  • Für Überladungen (3,4) ist der zweite Bereich [ first2 , last2 ) .
1,3) Elemente werden mit operator == verglichen.
2,4) Elemente werden mit dem gegebenen binären Prädikat p verglichen.

Wenn ForwardIt1 und ForwardIt2 unterschiedliche Werttypen haben, ist das Programm fehlerhaft.

Wenn die Vergleichsfunktion keine Äquivalenzrelation ist, ist das Verhalten undefiniert.

Inhaltsverzeichnis

Parameter

first1, last1 - das Paar von Iteratoren, das den ersten Bereich der zu vergleichenden Elemente definiert
first2, last2 - das Paar von Iteratoren, das den zweiten Bereich der zu vergleichenden Elemente definiert
p - binäres Prädikat, das ​ true zurückgibt, wenn die Elemente als gleich behandelt werden sollen.

Die Signatur der Prädikatfunktion sollte äquivalent zu Folgendem sein:

bool pred ( const Type1 & a, const Type2 & b ) ;

Obwohl die Signatur keine const & benötigt, darf die Funktion die übergebenen Objekte nicht modifizieren und muss alle Werte der Typen (möglicherweise const) Type1 und Type2 unabhängig von der Wertkategorie akzeptieren können (daher ist Type1 & nicht erlaubt , ebenso wenig wie Type1 , es sei denn, für Type1 ist eine Verschiebung äquivalent zu einer Kopie (seit C++11) ).
Die Typen Type1 und Type2 müssen so beschaffen sein, dass Objekte der Typen InputIt1 und InputIt2 dereferenziert und dann implizit in Type1 bzw. Type2 konvertiert werden können. ​

Typanforderungen
-
ForwardIt1, ForwardIt2 müssen die Anforderungen von LegacyForwardIterator erfüllen.

Rückgabewert

true falls der Bereich [ first1 , last1 ) eine Permutation des Bereichs [ first2 , last2 ) ist, false andernfalls.

Komplexität

Gegeben N als std:: distance ( first1, last1 ) :

1) Genau N Vergleiche mit operator == wenn die beiden Bereiche gleich sind, andernfalls O(N 2
) Vergleiche im schlimmsten Fall.
2) Genau N Anwendungen des Prädikats p wenn die beiden Bereiche gleich sind, andernfalls O(N 2
) Anwendungen im schlimmsten Fall.
3,4) Falls ForwardIt1 und ForwardIt2 beide LegacyRandomAccessIterator sind und last1 - first1 ! = last2 - first2 true ist, werden keine Vergleiche durchgeführt.
Andernfalls:
3) Genau N Vergleiche mit operator == wenn die beiden Bereiche gleich sind, andernfalls O(N 2
) Vergleiche im schlimmsten Fall.
4) Genau N Anwendungen des Prädikats p wenn die beiden Bereiche gleich sind, andernfalls O(N 2
) Anwendungen im schlimmsten Fall.

Mögliche Implementierung 

template<class ForwardIt1, class ForwardIt2>
bool is_permutation(ForwardIt1 first, ForwardIt1 last,
                    ForwardIt2 d_first)
{
    // gemeinsamen Präfix überspringen
    std::tie(first, d_first) = std::mismatch(first, last, d_first);
    // über den Rest iterieren, zählend wie oft jedes Element
    // aus [first, last) in [d_first, d_last) erscheint
    if (first != last)
    {
        ForwardIt2 d_last = std::next(d_first, std::distance(first, last));
        for (ForwardIt1 i = first; i != last; ++i)
        {
            if (i != std::find(first, i, *i))
                continue; // dieses *i wurde bereits geprüft
            auto m = std::count(d_first, d_last, *i);
            if (m == 0 || std::count(i, last, *i) != m)
                return false;
        }
    }
    return true;
}

Hinweis

Die std::is_permutation kann im Testen verwendet werden, nämlich um die Korrektheit von Umordnungsalgorithmen (z.B. Sortieren, Mischen, Partitionieren) zu überprüfen. Wenn x ein ursprünglicher Bereich und y ein permutierter Bereich ist, dann bedeutet std :: is_permutation ( x, y ) == true , dass y aus "denselben" Elementen besteht, die möglicherweise an anderen Positionen stehen.

Beispiel

Diesen Code ausführen 
#include <algorithm>
#include <iostream>
template<typename Os, typename V>
Os& operator<<(Os& os, const V& v)
{
    os << "{ ";
    for (const auto& e : v)
        os << e << ' ';
    return os << '}';
}
int main()
{
    static constexpr auto v1 = {1, 2, 3, 4, 5};
    static constexpr auto v2 = {3, 5, 4, 1, 2};
    static constexpr auto v3 = {3, 5, 4, 1, 1};
    std::cout << v2 << " ist eine Permutation von " << v1 << ": " << std::boolalpha
              << std::is_permutation(v1.begin(), v1.end(), v2.begin()) << '\n'
              << v3 << " ist eine Permutation von " << v1 << ": "
              << std::is_permutation(v1.begin(), v1.end(), v3.begin()) << '\n';
}

Ausgabe: 

{ 3 5 4 1 2 } ist eine Permutation von { 1 2 3 4 5 }: true
{ 3 5 4 1 1 } ist eine Permutation von { 1 2 3 4 5 }: false

Siehe auch

erzeugt die nächstgrößere lexikografische Permutation eines Elementbereichs
(Funktions-Template)
erzeugt die nächstkleinere lexikografische Permutation eines Elementbereichs
(Funktions-Template)
(C++20)
spezifiziert, dass eine relation eine Äquivalenzrelation definiert
(Konzept)
(C++20)
bestimmt, ob eine Sequenz eine Permutation einer anderen Sequenz ist
(Algorithmus-Funktionsobjekt)