Вопрос по c++11, stl-algorithm, c++, lexicographic, permutation – std :: next_permutation Описание реализации

94

Мне было любопытно как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 элементов.

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

Эй, как ты извлек этот кусок кода? Когда я проверил #include & lt; алгоритма & gt ;, код был совершенно другим, который состоял из большего количества функций Manjunath

Ваш Ответ

5   ответов
1

Существует очевидная возможная реализация на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, если его не существует.

7

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

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

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

Это подчеркивает важность хороших имен переменных и разделения интересов.is_final_permutation более информативен, чемbegin == end - 1, призваниеis_sorted_until/upper_bound отделяет логику перестановок от этих операций и делает это гораздо более понятным. Кроме того, upper_bound - это бинарный поиск, аwhile (!(*i < *--k)); линейный, так что это более производительный.
35

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

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l. Swap a[k] with a[l]. Reverse the sequence from a[k + 1] up to and including the final element a[n].
AFAICT, все реализации генерируют один и тот же порядок.
151

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

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
...

Как мы переходим от одной перестановки к другой? Во-первых, давайте посмотрим на вещи немного по-другому.We can view the elements as digits and the permutations as numbers, Просмотр проблемы таким образомwe want to order the permutations/numbers in "ascending" order.

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

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

Ага! Это ключ к пониманию алгоритма.We only change the position of a "digit" when everything to the right is in descending order because if it isn't in descending order then there are still more permutations to go (то есть мы можем «увеличить» перестановку на меньшую величину).

Теперь вернемся к коду:

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) часть.

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

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

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

Мы видим, что когда все справа от цифры в порядке убывания, мыfind the next largest digit and put it in front а потомput the remaining digits in ascending order.

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

It k = end;

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

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

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

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

хорошее объяснение & # xFF01;
В чем сложность такого алгоритма?
Удивительное объяснение
Спасибо за объяснение кода.
Спасибо за объяснение! Этот алгоритм называетсяGeneration in lexicographic order, Есть номера такого алгоритма вCombinatorics, но это самый классический.
11

Кнут подробно изучает этот алгоритм и его обобщения в разделах 7.2.1.2 и 7.2.1.3The Art of Computer Programming, Он называет это «Алгоритм L». - По-видимому, это относится к 13 веку.

Можете ли вы назвать название книги?
TAOCP = Искусство компьютерного программирования

Похожие вопросы