std::next_permutation Описание реализации

Question

std::next_permutation Описание реализации

Мне было любопытно как std:next_permutation был реализован таким образом, я извлек gnu libstdc++ 4.7 версия и санация идентификаторов и форматирования для создания следующей демонстрации...

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename It>
bool next_permutation(It begin, It end)
{
        if (begin == end)
                return false;

        It i = begin;
        ++i;
        if (i == end)
                return false;

        i = end;
        --i;

        while (true)
        {
                It j = i;
                --i;

                if (*i < *j)
                {
                        It k = end;

                        while (!(*i < *--k))
                                /* pass */;

                        iter_swap(i, k);
                        reverse(j, end);
                        return true;
                }

                if (i == begin)
                {
                        reverse(begin, end);
                        return false;
                }
        }
}

int main()
{
        vector<int> v = { 1, 2, 3, 4 };

        do
        {
                for (int i = 0; i < 4; i++)
                {
                        cout << v[i] << " ";
                }
                cout << endl;
        }
        while (::next_permutation(v.begin(), v.end()));
}

Результат такой, как и ожидалось: http://ideone.com/4nZdx

Мои вопросы: как это работает? Каково значение i, j а также k? Какую ценность они имеют в разных частях исполнения? Что такое набросок доказательства его правильности?

Ясно, что перед входом в основной цикл он просто проверяет тривиальные случаи списка 0 или 1 элемента. При входе в основной цикл я указываю на последний элемент (не на один последний конец), а список имеет длину не менее 2 элементов.

Что происходит в теле основного цикла?

129

c++ c++11 permutation stl-algorithm lexicographic

Источник

user1131467 14 июл '12 в 10:37

6 ответов

Решение

Реализация gcc генерирует перестановки в лексикографическом порядке. Википедия объясняет это следующим образом:

Следующий алгоритм генерирует следующую перестановку лексикографически после данной перестановки. Это изменяет данную перестановку на месте.
Найдите наибольший индекс k такой, что a [k]
Найдите наибольший индекс l такой, что a [k]
Поменяйте местами [k] с [l].
Переверните последовательность от a[k + 1] до последнего элемента a [n] включительно.

46

Источник

user819272 14 июл '12 в 10:56

Кнут подробно изучает этот алгоритм и его обобщения в разделах 7.2.1.2 и 7.2.1.3 "Искусства компьютерного программирования". Он называет это "Алгоритм L" - очевидно, он восходит к 13 веку.

12

Источник

22 янв '14 в 02:47

Вот полная реализация с использованием других стандартных библиотечных алгоритмов:

template <typename I, typename C>
    // requires BidirectionalIterator<I> && Compare<C>
bool my_next_permutation(I begin, I end, C comp) {
    auto rbegin = std::make_reverse_iterator(end);
    auto rend = std::make_reverse_iterator(begin);
    auto next_unsorted = std::is_sorted_until(rbegin, rend, comp);
    bool at_final_permutation = (next_unsorted == rend);
    if (!at_final_permutation) {
        auto next_permutation = std::upper_bound(
            rbegin, next_unsorted, *next_unsorted, comp);
        std::iter_swap(next_unsorted, next_permutation);
    }
    std::reverse(rbegin, next_unsorted);
    return !at_final_permutation;
}

демонстрация

9

Источник

user4859885 21 сен '15 в 12:36

Существует очевидная возможная реализация cppreference с использованием <algorithm>,

template <class Iterator>
bool next_permutation(Iterator first, Iterator last) {
    if (first == last) return false;
    Iterator i = last;
    if (first == --i) return false;
    while (1) {
        Iterator i1 = i, i2;
        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;
        }
    }
}

Измените содержимое на лексикографически следующую перестановку (на месте) и верните true, если существует; сортируйте и возвращайте false, если он не существует.

1

Источник

user2425366 21 сен '15 в 12:58

      #include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int main() {

    int int_array_11[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
    do {
        copy(begin(int_array_11), end(int_array_11), ostream_iterator<int>(cout, " "));
        cout << endl;
    } while (next_permutation(begin(int_array_11), end(int_array_11)));

    return 0;
}

-1

Источник

user7808151 11 май '22 в 06:38

Другие вопросы по тегам c++ c++11 permutation stl-algorithm lexicographic

user622647 14 июл '12 в 11:32 2012-07-14 11:32 · Accepted Answer · 2012-07-14 11:32

Давайте посмотрим на некоторые перестановки:

Как мы переходим от одной перестановки к другой? Во-первых, давайте посмотрим на вещи немного по-другому. Мы можем рассматривать элементы как цифры, а перестановки - как числа. Рассматривая проблему таким образом, мы хотим упорядочить перестановки / числа в "возрастающем" порядке.

Когда мы заказываем номера, мы хотим "увеличить их на минимальную сумму". Например, при подсчете мы не считаем 1, 2, 3, 10, ... потому что между ними по-прежнему есть 4, 5, ... и хотя 10 больше 3, существуют пропущенные числа, которые можно получить с помощью увеличивая 3 на меньшее количество. В приведенном выше примере мы видим, что 1 остается в качестве первого числа в течение длительного времени, поскольку существует много переупорядочений последних 3 "цифр", которые "увеличивают" перестановку на меньшую величину.

Так, когда мы наконец "используем" 1? Когда нет только перестановок последних 3 цифр.
И когда больше нет перестановок последних 3 цифр? Когда последние 3 цифры находятся в порядке убывания.

Ага! Это ключ к пониманию алгоритма. Мы меняем положение "цифры" только тогда, когда все справа находится в порядке убывания, потому что, если он не находится в порядке убывания, то есть еще больше перестановок (т.е. мы можем "увеличить" перестановку на меньшую величину),

Давайте теперь вернемся к коду:

while (true)
{
    It j = i;
    --i;

    if (*i < *j)
    { // ...
    }

    if (i == begin)
    { // ...
    }
}

Из первых 2 строк в цикле, j это элемент и i это элемент перед ним.
Затем, если элементы расположены в порядке возрастания, (if (*i < *j)) сделай что-нибудь.
В противном случае, если все в порядке убывания, (if (i == begin)) то это последняя перестановка.
В противном случае мы продолжаем и видим, что j и i существенно уменьшаются.

Теперь мы понимаем if (i == begin) часть, так что все, что нам нужно понять, это if (*i < *j) часть.

Также обратите внимание: "Тогда, если элементы расположены в порядке возрастания...", что подтверждает наше предыдущее наблюдение о том, что нам нужно только что-то сделать с цифрой "когда все направо в порядке убывания". Восходящий порядок if По сути, оператор находит самое левое место, где "все направо в порядке убывания".

Давайте снова посмотрим на некоторые примеры:

...
1 4 3 2
2 1 3 4
...
2 4 3 1
3 1 2 4
...

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

Давайте посмотрим на код:

It k = end;

while (!(*i < *--k))
    /* pass */;

iter_swap(i, k);
reverse(j, end);
return true;

Ну, так как все в порядке в порядке убывания, чтобы найти "следующую наибольшую цифру", мы просто должны пройтись с конца, что мы видим в первых 3 строках кода.

Затем мы поменяем местами "следующую наибольшую цифру" с iter_swap() утверждение, а затем, поскольку мы знаем, что цифра была следующей по величине, мы знаем, что цифры справа все еще находятся в порядке убывания, поэтому, чтобы поместить их в порядке возрастания, нам просто нужно reverse() Это.