Несмотря на большое количество недочётов у прошлой заметки о
перестановках, я подумал, что мой рассказ остался бы незавершённым без
попытки также максимально просто и наглядно объяснить полный алгоритм всех
перестановок, но уже в лексикографическом порядке.
Некоторые считают, что алгоритмы часто легче понять без слов, т.е.,
как говорят математики о каком-нибудь явлении: «это легко видеть».
Возможно, что это действительно так, но скорее всего, «это легко видеть» только
тем, кто медитирует перед учебниками по несколько часов в день.
Вновь отложим толстые учебники по комбинаторике и алгоритмам и
возьмем любимый пример с четырьмя цифрами. Будем считать, что наш
входной алфавит уже отсортирован в алфавитном порядке — 1,2,3,4.
Чтобы легче было понять код, который будет приведен ниже, снова до винтика
опишем каждое действие, которое мы проделываем на листке бумаги.
Итак, задача: найти все перестановки — 1,2,3,4, количество которых равно
факториалу 4! = 1*2*3*4 = 24
Решение:
1) Будем двигаться с конца массива, т.е. от 4 к 1 и сравнивать текущий и предыдущий элементы.
Нам важно узнать, не является ли предыдущий элемент большим, чем текущий.
Если текущий элемент — 3 меньше предыдущего — 4 ( кратко: 3 < 4 ), то будем
искать после текущего элемента — 3 — такой элемент, который минимально больше текущего, т.е.
на первой итерации это и будет 4.
2) Обменяем этот минимально больший элемент — 4 на текущий — 3, получим: 1,2,4,3.
3)А теперь отсортируем по возрастанию все после текущей позиции, т.е. после 4, иначе говоря,
отсортируем по возрастанию единственный элемент — 3. Получим ту же самую перестановку — 1,2,4,3,
(но так будет только на первой итерации).
4) Напечатаем результат и вернемся к перебору массива.
При следующем повторе согласно этому алгоритму получим 1,3,2,4.
Повторю: так как в перестановке 1,2,4,3 — 2 < 4, а число 3 минимально большее, чем 2, мы меняем
2 на 3 и сортируем хвост по возрастанию — все после 3 (4 и 2), получаем 1,3,2,4.
Анимация для закрепления:
Теперь сам код. Меня убеждали, что без функции goto не обойтись и вообще сделать такое слишком сложно, но, похоже, PHP
позволяет получить полный алгоритм перебора перестановок в лексикографическом порядке без этой конструкции goto.
Особенности:
1) Сделаем обычный цикл перебора массива с конца с сохранением ключей,
используем array_reverse.
для поиска минимально большего элемента будем каждый раз создавать промежуточный массив из исходного, будем использовать array_slice,
сортировать его и искать в нем элемент больше заданного.
2) Далее найдем ключ этого элемента в основном массиве — array_search
и поменяем местами элементы.
3) Затем разобьем основной массив на 2, отсортируем хвост и соберем обратно — array_merge.
4) Напечатаем вывод и оборвем цикл.
Так мы найдем одну перестановку, а для зацикливания найдем сначала факториал
всех элементов с помощью рекурсивной функции и обернем нашу конструкцию еще одним циклом до n!..
В итоге получим три цикла. Код получился без рекурсии.
Минусы: довольно много операций, что не может не сказаться на времени выполнения. Факториал все же лучше считать циклом или готовой функцией.
Однако ошибка о нехватке памяти уже не вылетает при n > 9, как с многими рекурсивными алгоритмами.
Но все равно скрипт значительно медленнее того, что был в предыдущей статье.
Прошлый скрипт за за 4-7 минут сгенерировал число перестановок для n = 11.
<?php < ? $a = array(1,2,3,4,5 ); $n = count($a); print_r($a); echo '<br />'; function factorial($n) { return $n ? $n * factorial($n - 1) : 1; } $fact = factorial($n); $l = 0; while ($l != $fact) { foreach(array_reverse($a, true) as $k => $v) { if ($k < count($a) - 1 && $v < $a[$k + 1]) { $b = array_slice($a, $k); sort($b); foreach($b as $key => $val) { if ($val > $v) { break; } } $x = array_search($val, $a); list($a[$k], $a[$x]) = array( $a[$x], $a[$k] ); $c = array_slice($a, 0, $k + 1); $d = array_slice($a, $k + 1); sort($d); $a = array_merge($c, $d); print_r($a); echo '<br />'; break; } } ++$l; } echo '<br />' . $l; ?> Post Scriptum
В заключение любителям перестановок хотел бы рекомендовать вот этот тему:
forum.ru-board.com/topic.cgi?forum=31&topic=16348
Считаю, что код на PHP человека с никнеймом Jokerjar79 написан мастерски.
А вот эта жемчужина уже на bash:
stackoverflow.com/questions/3846123/generating-permutations-using-bash
ссылка на оригинал статьи http://habrahabr.ru/post/260997/
Добавить комментарий