std::next_permutation — cppreference.com

Материал из cppreference.com

Определено в заголовочном файле `<algorithm>`
`template< class BidirIt > bool next_permutation( BidirIt first, BidirIt last );`	(1)
`template< class BidirIt, class Compare > bool next_permutation( BidirIt first, BidirIt last, Compare comp );`	(2)

Преобразование диапазона [first, last) в следующем перестановку из множества всех перестановок, которые лексикографически упорядочены по operator< или comp. Возврат true если такие перестановки существует, иначе превращает диапазон в первую перестановку (как бы std::sort(first, last)) и возвращается false.

Оригинал:

Transforms the range [first, last) into the next permutation from the set of all permutations that are lexicographically ordered with respect to operator< or comp. Returns true if such permutation exists, otherwise transforms the range into the first permutation (as if by std::sort(first, last)) and returns false.

Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

Параметры

first, last	—	диапазон элементов переставлять Оригинал: the range of elements to permute Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
comp	—	объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает `true`, если первый аргумент "меньше", чем второй. Определение сравнения должно быть эквивалентно: `bool cmp(const Type1 &a, const Type2 &b);` Использование `noexcept` (начиная с C++11) желательно но не обязательно. Параметры не обязаны передаваться по `const&`, но не должны модифицироваться. Они должны быть способны принимать все значения типа (даже `const`) `Type1` и `Type2` независимо от категории значений (таким образом, `Type1&` не допускается, равно как и `Type1`, если только для `Type1` перемещение не эквивалентно копированию (начиная с C++11)). Типы `Type1` и `Type2` должны быть таковы, что объект типа `BidirIt` может быть разыменован и затем неявно преобразован в оба из них.
Требования к типам
-`BidirIt` должен соответствовать требованиям `ValueSwappable` и `BidirectionalIterator`.

Возвращаемое значение

true если новые перестановки лексикографически больше, чем старые. false если последняя перестановка была достигнута, и диапазон был сброшен в первую перестановку.

Оригинал:

true if the new permutation is lexicographically greater than the old. false if the last permutation was reached and the range was reset to the first permutation.

Сложность

В большинстве перестановокN/2, где N = std::distance(first, last).

Оригинал:

At most N/2 swaps, where N = std::distance(first, last).

Возможная реализация

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    if (first == last) return false;
    BidirIt i = last;
    if (first == --i) return false;

    while (1) {
        BidirIt i1, i2;

        i1 = i;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

Пример

Следующий код выводит все три перестановки строки "аба"

Оригинал:

The following code prints all three permutations of the string "aba"

#include <algorithm>
#include <string>
#include <iostream>

int main()
{
    std::string s = "aba";
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << '\n';
    } while(std::next_permutation(s.begin(), s.end()));
}

Вывод:

См. также

	определяет, является ли последовательность перестановкой другой последовательности (шаблон функции) [править]
	генерирует следующую меньшую лексикографическую перестановку диапазона элементов (шаблон функции) [править]

Категории: