Мне было любопытно, как это 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 указывает на последний элемент (а не на один конец), и список состоит как минимум из двух элементов.
Что происходит в теле основного цикла?
c++
c++11
permutation
stl-algorithm
lexicographic
Эндрю Томазос
источник
источник
Ответы:
Давайте посмотрим на некоторые перестановки:
Как нам перейти от одной перестановки к другой? Во-первых, давайте посмотрим на вещи немного по-другому. Мы можем рассматривать элементы как цифры, а перестановки как числа . Рассматривая проблему таким образом, мы хотим упорядочить перестановки / числа в «возрастающем» порядке .
Заказывая номера, мы хотим «увеличить их на наименьшую сумму». Например, при подсчете мы не считаем 1, 2, 3, 10, ... потому что все еще есть 4, 5, ... между ними, и хотя 10 больше 3, есть недостающие числа, которые можно получить увеличивая 3 на меньшую величину. В приведенном выше примере мы видим, что оно
1
остается первым номером в течение длительного времени, поскольку есть много перестановок последних 3 «цифр», которые «увеличивают» перестановку на меньшую величину.Итак, когда мы наконец "используем"
1
? Когда больше нет перестановок последних 3 цифр.А когда больше нет перестановок последних 3 цифр? Когда последние 3 цифры расположены в порядке убывания.
Ага! Это ключ к пониманию алгоритма. Мы изменяем положение «цифры» только тогда, когда все справа находится в порядке убывания, потому что, если это не в порядке убывания, то есть еще другие перестановки (т.е. мы можем «увеличить» перестановку на меньшую величину) .
Вернемся к коду:
Из первых двух строк цикла
j
- это элемент, аi
это элемент перед ним.Затем, если элементы расположены в порядке возрастания, (
if (*i < *j)
) что-то делает.В противном случае, если все идет в порядке убывания (
if (i == begin)
), то это последняя перестановка.В противном случае мы продолжаем и видим, что j и i существенно уменьшаются.
Теперь мы понимаем
if (i == begin)
часть, поэтому все, что нам нужно понять, этоif (*i < *j)
часть.Также обратите внимание: «Тогда, если элементы расположены в порядке возрастания ...», что подтверждает наше предыдущее наблюдение, что нам нужно сделать что-то только с цифрой, «когда все справа находится в порядке убывания». Оператор восходящего порядка
if
по сути находит крайнее левое место, где «все справа находится в порядке убывания».Давайте еще раз посмотрим на несколько примеров:
Мы видим, что когда все справа от цифры находится в порядке убывания, мы находим следующую по величине цифру и помещаем ее впереди, а затем помещаем оставшиеся цифры в порядке возрастания .
Посмотрим на код:
Что ж, поскольку элементы справа расположены в порядке убывания, чтобы найти «следующую по величине цифру», нам просто нужно выполнить итерацию с конца, что мы видим в первых трех строках кода.
Затем мы меняем «следующую по величине цифру» на передний план с помощью
iter_swap()
оператора, а затем, поскольку мы знаем, что эта цифра была следующей по величине, мы знаем, что цифры справа все еще находятся в порядке убывания, поэтому, чтобы поместить их в порядке возрастания, мы просто должныreverse()
это сделать.источник
Combinatorics
, но он самый классический.Реализация gcc генерирует перестановки в лексикографическом порядке. Википедия объясняет это следующим образом:
источник
Кнут подробно описывает этот алгоритм и его обобщения в разделах 7.2.1.2 и 7.2.1.3 книги «Искусство компьютерного программирования» . Он называет это «Алгоритм L» - очевидно, он восходит к 13 веку.
источник
Вот полная реализация с использованием других алгоритмов стандартной библиотеки:
Демо
источник
is_final_permutation
информативнее чемbegin == end - 1
. Вызовis_sorted_until
/upper_bound
отделяет логику перестановки от этих операций и делает это гораздо более понятным. Кроме того, upper_bound - это двоичный поиск, аwhile (!(*i < *--k));
линейный поиск - более производительный.Существует очевидная возможная реализация с использованием cppreference
<algorithm>
.Измените содержимое на лексикографически следующую перестановку (на месте) и верните истину, если существует, в противном случае сортируйте и верните ложь, если она не существует.
источник