Изменения

Перейти к: навигация, поиск

Получение следующего объекта

224 байта добавлено, 10:03, 20 декабря 2011
→‎Специализация алгоритма для генерации следующей перестановки
== Специализация алгоритма для генерации следующей перестановки ==
Двигаемся справа налево по элементам объекта, пока не найдем элемент, нарушающий убывающую последовательность. Обменяем его с минимальным элементом, большим нашего, стоящим правее. Далее перевернем правую часть.
* Двигаясь справа налево, находим элаемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример)
* Меняем его с минимальным элементом, большим нашего, стоящим правее
* Перевернем правую часть
<code>
bool next_permutation(vector<int> &a) { int n = a.size(); int pos for i = n - 2; 1 downto 1 while (pos != -1 && if a[posi] > < a[pos i + 1]) --pos; if (pos // a[j] == -1) return false; int k = n - 1; while (min {a[posj] > a[ki]) --k;, где j > i} swap(a[posi], a[kj]); int l = pos + 1, r = n - 1; while (l < r) swap reverse(a[l+i +1], .. a[r--n]); return true; } break
</code>
=== Пример работы ===
Free0u
117
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/14962»

Навигация