Как работает next_permutation в С++?
Кто в курсе, можете рассказать, как работает next_permutation в С++? Зачем этой функции нужны два итератора? Где она хранит состояние между вызовами. Сейчас пилил just for fun такую штуку на шарпе и стало интересно.
beaver ☆
04.10.19 17:00:36 MSK
Meyer ★★★★★
( 04.10.19 17:14:42 MSK )
Последнее исправление: Meyer 04.10.19 17:16:42 MSK (всего исправлений: 1)
Ну так скачайте исходники gcc и найдите там как реализовано, в отличии от всяких там непосредственно кодов компилятора, исходные коды STL библиотеки, в реализации от GCC читаются легко, непренуждённо и увлекатльно.
p.s. кодю на C++ уже как 3-й год наверное, в т.ч. по основной работе, активно юзаю STL, а о такой штуке как next_permutation даже и не слышал 🙂
bonta ★★★★★
( 04.10.19 17:15:05 MSK )
Поведение функции соотвествует следующей перестановки только в том случае, если все элементы разные в соответствии с operator
А в этом случае состояние описывается упорядоченностью элементов и хранить отдельно его не нужно.
GPFault ★★
( 04.10.19 20:15:14 MSK )
Ответ на: комментарий от bonta 04.10.19 17:15:05 MSK
исходные коды STL библиотеки, в реализации от GCC читаются легко, непренуждённо и увлекатльно.
Вот совсем нет. Стиль оформления кода у них настолько чудовищный, что исходники читаются только чуть лучше, чем никак.
m0rph ★★★★★
( 04.10.19 20:28:05 MSK )
Ответ на: комментарий от GPFault 04.10.19 20:15:14 MSK
Поведение функции соотвествует следующей перестановки только в том случае, если все элементы разные в соответствии с operator
Я только пытаюсь понять функцию, но на cppreference пример переставляет строку std::sort(«aba») :
aab aba baa Алгоритмы стандартной библиотеки C++
Заголовочный файл algorithm содержит много полезных алгоритмов.
Большинство из этих алгоритмов принимают в качестве параметра два итератора, будем обозначать их first и last. В этом случае алгоритм работает с элементами контейнера от first включительно до last невключительно. Чаще всего в качестве first используется метод begin(), а в качестве last — метод end(), в этом случае алгоритм применяется ко всему контейнеру. Например,
Используя операции «+» и «-» для итераторов можно применять алгоритмы не для всего контейнера, а для части.
Можно передавать также reverse_iteraror, наиболее употребительный способ использования — это сортировка в обратном порядке при помощи:
Алгоритмы поиска
find
Алгоритм find(first, last, val) осуществляет линейный поиск значения val от итератора first до итератора last . Элементы просматриваются последовательность, возвращается итератор на первый найденный элемент. Если элемент val не будет найден, то возвращается значение итератора last .
binary_search
Алгоритм binary_search(first, last, val) осуществляет двоичный поиск значения val . Контейнер должен быть упорядочен. Возвращается значение типа bool , то есть true или false в зависимости от того, есть ли такой элемент в контейнере.
lower_bound
Алгоритм lower_bound(first, last, val) осуществляет двоичный поиск значения val и возвращает итератор res на первый элемент, который не меньше, чем val , то есть *res>=val , a *(res-1)
upper_bound
Алгоритм upper_bound(first, last, val) осуществляет двоичный поиск значения val и возвращает итератор res на первый элемент, который строго больше, чем val , то есть *res>val , a *(res-1)
Алгоритмы сортировки, разворота, сдвига
sort
sort(first, last) — упорядочивает элементы контейнера по неубыванию.
stable_sort
sort(first, last) — упорядочивает элементы контейнера по неубыванию, при этом равные элементы не переставляются (так называемая «устойчивая сортировка»).
reverse
reverse(first, last) — разворачивает фрагмент контейнера в обратном порядке, переставляя элементы, равноудаленные от концов.
rotate
reverse(first, n_first, last) — осуществляет циклический сдвиг фрагмента контейнера. Элемент, на который указывает итератор n_first становится первым элементом (то есть переходит на место элемента first ), элемент n_first+1 — вторым и т.д.
Перестановки
next_permutation
next_permutation(first, last) — переставляет элементы так, чтобы получилась следующая в лексикографическом порядке перестановка. Можно применять не только к векторам, но и к строкам (как и многие другие алгоритмы). Метод возвращает true , если удалось построить следующую в лексикографическом порядке перестановку. Если же первоначальная перестановка уже была максимальной в лексикографическом порядке, то метод генерирует минимальную в лексикографическом порядке перестановку и возвращает false .
Например, вывести все перестановки в лексикографическом порядке можно так:
prev_permutation
prev_permutation(first, last) — переставляет элементы так, чтобы получилась предыдущая в лексикографическом порядке перестановка. Можно применять не только к векторам, но и к строкам (как и многие другие алгоритмы). Метод возвращает true , если удалось построить предыдущую в лексикографическом порядке перестановку. Если же первоначальная перестановка уже была минимальной в лексикографическом порядке, то метод генерирует максимальную в лексикографическом порядке перестановку и возвращает false .
random_shuffle
random_shuffle(first, last) — делает случайную перестановку элементов контейнера.
Минимальные и максимальные элементы, подсчет
min_element
Алгоритм min_element(first, last) находит минимальный элемент в контейнере и возвращает итератор на этот элемент. Если есть несколько элементов, равных минимальному, возвращается значение первого из них.
max_element
max_element(first, last) возвращает итератор на наибольший элемент. Если есть несколько элементов, равных наибольшему — то на первый из них.
count
count(first, last, val) — подсчитывает сколько элементов контейнера равны значению val .
Алгоритмы перестановок. Примеры
В алгоритме последовательность изменяется путём перестановки соседних элементов. Рассматриваются текущие и последующие элементы, которые затем переставляются на основе заданного условия. Условие может быть задано предикатом.
Алгоритм имеет две перегруженные реализации
template class BidirectionalIterator> bool next_permutation( BidirectionalIterator first, BidirectionalIterator last); template class BidirectionalIterator, class BinaryPredicate> bool next_permutation( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate pred);
- first , last – двунаправленные итераторы, определяющие начало и конец исследуемого диапазона. В пределах этого диапазона происходит перестановка элементов;
- pred – бинарный (двоичный) предикат, задающий критерий сравнения.
Пример.
#include iostream> #include queue> #include vector> #include list> #include functional> #include algorithm> using namespace std; // Предикат, определяющий условие алгоритма next_permutation bool Less_Than(int a, int b) < return a < b; >int main() < // Алгоритм next_permutation – сформировать последовательность // на основе правила замены текущей перестановки следующей перестановкой. // 1. Использование алгоритма без предиката // 1.1. Объявить исходный массив vectorint> V1 = < 9, 8, 7, 4, 5, 3, 1, 2 >; // 1.2. Вывести исходный массив cout «V1 => «; for (int i : V1) cout << i " "; cout // 1.2. Вызвать алгоритм next_permutation(V1.begin(), V1.begin() + 3); // сравниваются только первые 3 элемента // 1.3. Вывести результирующий массив cout «V1 => «; for (int i : V1) cout << i " "; cout // 2. Использование алгоритма с предикатом // 2.1. Объявить исходный массив vectorint> V2 = < 1, 2, 3, 4, 5, 6 >; // 2.2. Вызвать алгоритм на основе предиката Less_Than next_permutation(V2.begin(), V2.end(), Less_Than); // принимаются во внимание все элементы // 2.3. Вывести исходный массив cout «V2 => «; for (int i : V2) cout << i " "; cout
V1 => 9 8 7 4 5 3 1 2 V1 => 7 8 9 4 5 3 1 2 V2 => 1 2 3 4 6 5
⇑
2. Алгоритм prev_permutation . Сформировать последовательность на основе правила замены текущей перестановки предыдущей
Данный алгоритм отличается от предыдущего тем, что при перестановке элементов рассматриваются текущие и предыдущие элементы. Критерий перестановки может быть задан предикатом.
Алгоритм имеет две перегруженные реализации
template class BidirectionalIterator> bool prev_permutation( BidirectionalIterator first, BidirectionalIterator last); template BidirectionalIterator, class BinaryPredicate> bool prev_permutation( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate pred);
- first , last – двунаправленные итераторы, задающие диапазон в котором переставляются элементы;
- pred – бинарный (двоичный) предикат, задающий критерий сравнения.
Пример.
#include iostream> #include queue> #include vector> #include list> #include functional> #include algorithm> using namespace std; // Предикат, который определяет условие для алгоритма prev_permutation bool Less_Than(int a, int b) < return a < b; >int main() < // Алгоритм prev_permutation – формирует последовательность таким образом, // что текущая перестановка заменяется предыдущей большей (меньшей) перестановкой, // если таковая имеется. Критерий сравнения (больше, меньше) задается бинарным предикатом. // 1. Использование алгоритма без предиката // 1.1. Объявить исходный массив vectorint> V1 = < 1, 2, 3, 4, 5, 6, 8, 9 >; // 1.2. Вызвать алгоритм prev_permutation(V1.begin(), V1.begin() + 3); // сравниваются только первые 3 элемента // 1.3. Вывести исходный массив cout «V1 => «; for (int i : V1) cout << i <" "; cout // 2. Использование алгоритма с предикатом // 2.1. Объявить исходный массив vectorint> V2 = < 1, 2, 3, 4, 5, 6 >; // 2.2. Вызвать алгоритм на основе предиката Less_Than prev_permutation(V2.begin(), V2.end(), Less_Than); // принимаются ко вниманию все элементы // 2.3. Вывести исходный массив cout «V2 => «; for (int i : V2) cout << i " "; cout
V1 => 3 2 1 4 5 6 8 9 V2 => 6 5 4 3 2 1
⇑
Связанные темы
- Алгоритмы работы с данными которые представлены по принципу «кучи» (heap). Алгоритмы make_heap , push_heap , pop_heap , sort_heap
- Алгоритмы определения минимума и максимума. Алгоритмы min , min_element , max , max_element , lexicographical_compare
- Немодифицирующие алгоритмы. Поиск. Алгоритмы find , find_if , find_first_of , find_end , adjanced_find , search , search_n
- Немодифицирующие алгоритмы. Алгоритмы count , count_if , equal , equal_range , mismatch
- Алгоритмы для работы с множествами. Алгоритмы includes , set_union , set_intersection , set_difference , set_symmetric_difference
Алгоритм: Как найти следующую лексикографическую перестановку
Если кратко описать, что такое лексикографический порядок — это сортировка в алфавитном порядке. Т.е. последовательность символов — AAA → AAB → AAC → AAD → ……… → WWW — является отсортированной в алфавитном (или в нашем случае лексикографическом) порядке.
Представьте, что у Вас есть конечная последовательность символов, например 0, 1, 2, 5, 3, 3, 0 и Вам необходимо найти все возможные перестановки этих символов. Наиболее интуитивным, но и наибольшим по сложности, является рекурсивный алгоритм, когда мы выбираем первый символ из последовательности, далее рекурсивно выбираем второй, третий итд, до тех пор, пока все символы из последовательности не будет выбраны. Понятно, что сложность такого алгоритма — O(n!).
Но оказывается, что наиболее простой алгоритм генерации всех перестановок в лексикографическом порядке — это начать с наименьшей и многократно вычислять следующую перестановку на месте. Давайте посмотрим как это сделать.
Точно также, как при расчете следующего целочисленного значения, мы должны стараться увеличить правую часть последовательности и оставить левую часть неизменной.
В качестве примера возьмем вышеприведенную последовательность — (0, 1, 2, 5, 3, 3, 0). Чтобы получить последовательность выше оригинальной, достаточно переставить первый и второй элементе местами, но в этом нет необходимости, так как можно переставить второй и и третий и получив более близкую по возрастанию последовательность. что приведет нас к следующей более близкой перестановки итд.
Наиболее оптимальным алгоритмом в этом случае будет следующий:
- Прежде всего Вы должны найти наибольший не-увеличивающийся суффикс. В вышеприведенном примере это будет — (5, 3, 3, 0). Если Вы попробуете сделать любую перестановку в данной последовательности, то она не будет выше оригинальной.
Стоит сказать, что найти данную последовательность вы можете за O(n) времени, просматривая последовательность слева направо. - Следующий элемент от суффикса является точкой поворота. В нашем случае — это 2. Точка поворота будет всегда меньше первого элемента суффикса. Это значит, что в суффиксе обязательно будет элемент превышающий точку поворота и если мы поменяет точку поворота на наименьший элемента из суффикса, превышающий опорный элемент точки поворота — мы получим последовательность превышающую оригинальную — в нашем случает это будет — (0, 1, 3, 5, 3, 2, 0).
Т.е. результатом этой операции будет минимально возможный по возрастанию префикс. - И на последнем шаге мы должны отсортировать суффикс в порядке возрастания. Т.е. мы получим минимально возможный суффикс. В нашем примере это будет (0, 2, 3, 5) и вся последовательность будет выглядеть как (0, 1, 3, 0, 2, 3, 5).
Это значение и будет следующей лексикографической перестановкой.
Что касается практического применения алгоритма, то за все время моей работы он мне ни разу не понадобился, но на интервью в Uber посчитали иначе :))
Для простоты весь код будет написан на Go и думаю никому не составить труда перевести его на любой другой язык программирования.
Большое спасибо PYXRU и 646f67, что ткнули меня носом в возможную оптимизацию алгоритма — произвести расчет перестановки за линейную сложность просто сделав reverse суффикса.
func NextPermutationAlgorithm(w string) string < l := len(w) b := []byte(w) r := "no answer" for i:=l-1; i>0 ; i-- < if b[i-1] < b[i] < pivot := i for j := pivot; j < l; j++ < if b[j] > b[i-1], b[pivot] = b[pivot], b[i-1] for j := l-1; i < j; i, j = i+1, j-1 < b[i], b[j] = b[j], b[i] >r = string(b) break > > return r > - алгоритм
- go
- лексикографическая перестановка
- next permutation algorithm