Получение следующего объекта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Удалено содержимое страницы)
Строка 1: Строка 1:
== Определение ==
 
'''Получение следующего объекта''' - это нахождение следующего объекта в лексикографическом порядке.
 
  
== Алгоритм ==
 
Находим максимальный общий префикс, после него ставим минимальный возможный элемент и дописываем минимальный возможный хвост.
 
 
----
 
 
== Пример (перестановки) ==
 
 
Каждая следующая перестановка строится следующим образом:
 
 
Двигаясь с конца массива сравниваем соседние элементы, если 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 Википедия - свободная энциклопедия]
 

Версия 01:34, 23 октября 2011