std::prev_permutation — cppreference.com

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

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

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

Оригинал:

Transforms the range [first, last) into the previous 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 last permutation (as if by std::sort(first, last); std::reverse(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 precedes the old in lexicographical order. false if the first permutation was reached and the range was reset to the last permutation.

Сложность

В большинстве свопы (last-first)/2.

Оригинал:

At most (last-first)/2 swaps.

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

template<class BidirIt>
bool prev_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 (*i1 < *--i) {
            i2 = last;
            while (!(*--i2 < *i))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

Пример

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

Оригинал:

The following code prints all six permutations of the string "abc" in reverse order

#include <algorithm>
#include <string>
#include <iostream>
#include <functional>
int main()
{
    std::string s="abc";
    std::sort(s.begin(), s.end(), std::greater<char>());
    do {
        std::cout << s << ' ';
    } while(std::prev_permutation(s.begin(), s.end()));
    std::cout << '\n';
}

Вывод:

См. также

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

Категории: