WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::next_permutation — nächste lexikografische Permutation

std::next_permutation ordnet einen Bereich in seine nächste lexikografische Permutation um. Die Funktion gibt true zurück, wenn eine Nachfolgepermutation existiert; nach der letzten Permutation stellt sie die erste Anordnung wieder her und gibt false zurück.

Version: C++23; repository compiler flag, production runtime not attested

Syntax

#include <algorithm>

template<class BidirectionalIterator>
constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

template<class BidirectionalIterator, class Compare>
constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

std::next_permutation aus <algorithm> verändert den Bereich [first, last) direkt. Für die lexikografische Reihenfolge zweier Anordnungen ist die erste Position entscheidend, an der die Elemente nach dem verwendeten Vergleich nicht äquivalent sind. Die Überladung ohne comp verwendet den standardmäßigen Kleiner-als-Vergleich; die Überladung mit comp legt die Ordnung mithilfe dieses Vergleichsoperators fest.

Ein Ergebnis von true bedeutet, dass eine Nachfolgepermutation gefunden wurde. Ein Ergebnis von false bedeutet nicht, dass die Daten unverändert bleiben: Der Algorithmus stellt die erste Anordnung wieder her, sortiert in aufsteigender Reihenfolge gemäß dem verwendeten Vergleich. Bei einem leeren Bereich oder einem Bereich mit nur einem Element wird false zurückgegeben.

Die Iteratoren müssen bidirektional sein, und die referenzierten Elemente müssen das Vertauschen von Werten unterstützen. comp muss eine strikte schwache Ordnung definieren; verwende nicht <=. Für N Elemente begrenzt der Standard die Anzahl der Vertauschungen auf N / 2.

Beginne mit einem gemäß demselben Vergleich sortierten Bereich und verwende do–while, damit auch die anfängliche Anordnung verarbeitet wird. Die Schleife durchläuft genau eine Anordnung für jede unterschiedliche Folge der durch den Vergleich definierten Äquivalenzklassen. Wenn der Vergleich ungleiche Werte als äquivalent behandelt, kann die Schleife manche unterschiedlichen Wertfolgen überspringen. Im Beispiel unterscheidet der Standardvergleich 1 und 2, daher gibt die Schleife alle drei unterschiedlichen Wertanordnungen aus. Das Beispiel zeigt auch den Zustand nach dem abschließenden Aufruf, der false zurückgibt.

Beispiele

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    std::array<int, 3> values{1, 1, 2};
    do {
        std::cout << values[0] << ' ' << values[1] << ' '
                  << values[2] << '\n';
    } while (std::next_permutation(values.begin(), values.end()));

    std::cout << "reset: " << values[0] << ' ' << values[1]
              << ' ' << values[2] << '\n';
}

Ergebnis

1 1 2
1 2 1
2 1 1
reset: 1 1 2

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen