Материал из Викиконспекты
|
|
| Строка 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
