LINUX.ORG.RU

Как работает next_permutation в С++?

 , ,


0

3

Кто в курсе, можете рассказать, как работает next_permutation в С++? Зачем этой функции нужны два итератора? Где она хранит состояние между вызовами. Сейчас пилил just for fun такую штуку на шарпе и стало интересно.


Ну так скачайте исходники gcc и найдите там как реализовано, в отличии от всяких там непосредственно кодов компилятора, исходные коды STL библиотеки, в реализации от GCC читаются легко, непренуждённо и увлекатльно.

p.s. кодю на C++ уже как 3-й год наверное, в т.ч. по основной работе, активно юзаю STL, а о такой штуке как next_permutation даже и не слышал :)

bonta ★★ ()

Поведение функции соотвествует следующей перестановки только в том случае, если все элементы разные в соответствии с operator<

А в этом случае состояние описывается упорядоченностью элементов и хранить отдельно его не нужно.

GPFault ()
Ответ на: комментарий от bonta

исходные коды STL библиотеки, в реализации от GCC читаются легко, непренуждённо и увлекатльно.

Вот совсем нет. Стиль оформления кода у них настолько чудовищный, что исходники читаются только чуть лучше, чем никак.

m0rph ★★★★★ ()
Ответ на: комментарий от GPFault

Поведение функции соотвествует следующей перестановки только в том случае, если все элементы разные в соответствии с operator<

Я только пытаюсь понять функцию, но на cppreference пример переставляет строку std::sort("aba"):

aab
aba
baa
KennyMinigun ★★★★★ ()
Ответ на: комментарий от KennyMinigun

Если на значения самих элементов не смотреть, а смотреть на них как на индексированные чёрные ящики - то перестановок не 3, а 6:

123
aab

132
aba

213
aab

231
aba

312
baa

321
baa

Если нужно переставлять элементы коллекции вне зависимости от её значений - то текущее поведение будет большим сюрпризом.

GPFault ()
Ответ на: комментарий от GPFault

А, понял. Спасибо за разьяснение.

текущее поведение будет большим сюрпризом

Ну там сразу декларируется лексикографичность(?) операции:

  • next_permutation - generates the next greater lexicographic permutation of a range of elements
  • prev_permutation - generates the next smaller lexicographic permutation of a range of elements
KennyMinigun ★★★★★ ()
Последнее исправление: KennyMinigun (всего исправлений: 1)

как работает next_permutation в С++?

Вычисляет следующую перестановку.

Зачем этой функции нужны два итератора?

Чтобы получить начало и конец последовательности.

Где она хранит состояние между вызовами.

Нигде не хранит.

Legioner ★★★★★ ()
Ответ на: комментарий от Legioner

Вычисляет следующую перестановку.

Каким образом?

Чтобы получить начало и конец последовательности.

Почему ему не хватает только ссылки на последовательность?

Нигде не хранит.

Как он тогда узнаёт, что текущая перестановка уже была и нужно вычислить новую?

beaver ()
Ответ на: комментарий от beaver

Почему ему не хватает только ссылки на последовательность?

Потому, что в C++ последовательность принято определять двумя итераторами, указывающими на начало и на конец.

Legioner ★★★★★ ()
Ответ на: комментарий от beaver

Чтобы получить начало и конец последовательности.

Почему ему не хватает только ссылки на последовательность?

Две причины:

  • Итераторы в С++ (по крайней мере стандартные) не знают о «размере» контейнера (они могут только перемещаться по контейнеру без проверки границ).
  • Весь STL спроектирован на итераторах, чтоб можно было проводить операции и на части контейнера. А понятие «range» появится в STL только в С++20.

Как он тогда узнаёт, что текущая перестановка уже была и нужно вычислить новую?

std::next_permutation делает лексикографическую перестановку (согласно operator < или соотвентствующего компаратора). Т.е. состояние перестановки == порядок значений последовательности.

KennyMinigun ★★★★★ ()