std:: следующее объяснение реализации перестановки

мне было интересно, как 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 список элементов. При входе в основной цикл i указывает на последний элемент (не один конец), и список имеет длину не менее 2 элементов.

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

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

5 ответов:

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

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

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

когда мы заказываем номера, мы хотим "увеличить их на наименьшее количество". Например, при подсчете мы не графа 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() его.

147

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

следующий алгоритм генерирует следующую перестановку лексикографически после данной перестановки. Он изменяет данное перестановка на месте.

  1. найти наибольший индекс k такой, что a[k]
  2. найти самый большой индекс l такой, что a[k]
  3. замените a[k] на A[l].
  4. обратный последовательность от a[k + 1] до и включая конечный элемент a[n].
34

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

11

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

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;
}

демо

6

там возможно толковый реализация на 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