Изменения

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

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

1694 байта убрано, 01:34, 23 октября 2011
Удалено содержимое страницы
== Определение ==
'''Получение следующего объекта''' - это нахождение следующего объекта в лексикографическом порядке.
== Алгоритм ==
Находим максимальный общий префикс, после него ставим минимальный возможный элемент и дописываем минимальный возможный хвост.
 
----
 
== Пример (перестановки) ==
 
Каждая следующая перестановка строится следующим образом:
 
Двигаясь с конца массива сравниваем соседние элементы, если a[i - 1] > a[i] двигаемся дальше, если a[i - 1] < a[i], m := i - 1(поскольку мы нашли m дальше не смысла двигаться) выходим из цикла.
k := i, такое что a[i] > a[m] и a[i] = min(a[i]), при i > m.
Меняем местами a[m] и a[k]
Осталось упорядочить по возрастанию элементы, стоящие справа от нового m-го элемента, но т.к. они упорядочены по убыванию, достаточно их обернуть.
----
 
 
 
== Ссылки ==
[http://rain.ifmo.ru/cat/view.php/vis/combinations/permutations-2000 Дискретная математика : алгоритмы]
 
[http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0 Википедия - свободная энциклопедия]
304
правки

Навигация