Перелистывая вопросы и статьи в Интернете, я обратил внимание, что эта простая на первый взгляд тема составляет некую трудность при составлении алгоритма. Попробую максимально просто объяснить себе и вам алгоритм генерации перестановок.
Многие статьи, описывающие тему перестановок, начинаются с формул или теории общей комбинаторики Отступим от этого канонического принципа.
Есть задача: требуется напечатать все перестановки чисел четырех чисел:
1, 2, 3, 4.
Решение — сначала на листке бумаги
1) Посчитаем последовательно перестановки для одного элемента, для — 1.
Запишем результат:
1
Он равен единице, один элемент переставлять некуда, но мы запомним результат, пригодится.
2) Посчитаем перестановки для двух элементов — 1 и 2
Запишем результат:
1 2
2 1
У нас две перестановки. Все перестановки из дух элементов равны двум. Теперь нужно посчитать для трех элементов — 1, 2, 3. Для этого возьмем наше новое число — 3 и подставим его в каждую строку к перестановкам для двух элементов.
Будем подставлять для каждой строки последовательно так, чтобы это число — 3 — побывало на каждой позиции, т. е.: в конце строки, между каждым элементом и в начале строки. Начнем с конца строки.
Для первой строки получим результат (в виде квадратной диагональной матрицы):
1 2 3
1 3 2
3 1 2
Для второй строки результат:
2 1 3
2 3 1
3 2 1
Запишем результат.
3) Для четырех элементов — 1, 2, 3, 4 осуществим все то же самое, что и на шаге два. Возьмем значения, полученные ранее и подставим цифру 4 для каждой строки в конце, между каждым элементом и в начале строки.
Снова начнем с конца:
1 2 3 4
1 2 4 3
1 4 2 3
4 1 2 3
1 3 2 4
1 3 4 2
1 4 3 2
4 1 3 2
3 1 2 4
3 1 4 2
3 4 1 2
4 3 1 2
2 1 3 4
2 1 4 3
2 4 1 3
4 2 1 3
2 3 1 4
2 3 4 1
2 4 3 1
4 2 3 1
3 2 1 4
3 2 4 1
3 4 2 1
4 3 2 1
Получим 24 перестановки. Легко проверить — факториал числа 4 равен 24:
4! = 1*2*3*4=24
Обратим еще раз внимание: мы берем результаты, найденные на предыдущем шаге, берем число выше на единицу, подставляем это число в каждую строку — тянем с конца строки в начало. Когда это число на первой позиции, мы берем следующую строку и повторяем действия. Получаем простой алгоритм перестановок в нелексикографическом порядке, который можно быстро перевести на машинный язык. Результат, кстати, сильно напоминает код Грея для перестановок, а также алгоритм Джонсона-Троттера. Хотя я не вникал сильно, но если интересно, то почитать о нем можно, набрав в поисковике «Коды Грея для перестановок».
Попрбуем реализовать этот алгоритм на PHP, для хранения значений будем использовать файлы. Создадим два файла с именами 1.txt и 2.txt, в файл 1.txt запишем единицу в таком виде — сначала точку в качестве разделителя, затем цифру — .1
Для каких-то практических задач использование нижеприведенного когда не планируется, поэтому навернем в нем всего побольше:
1. Будем читать файл 1.txt построчно.
2. Будем обрубать разделитель в самом начале (substr).
3. Оборвем цикл, если строка пустая.
4. Строку будем разбивать и хранить в массиве (explode).
5. К ней добавим следующее число (array_push).
Неприятный факт, но еще на каждой итерации самого верхнего цикла будем использовать array_trim, так как в массиве у нас неизвестным образом появляется символ проблела.
6. И циклы с перебором массивов (foreach), конечно, надо удалить, так как их наличие — это действительно жестоко, но мы понимаем это, а также то, что код писался ночью и только для демонстрации работы.
7. В цикле while будем использовать только list для смещения числа по строке.
8. Все результаты будем писать в файл 2.txt, затем удалим 1.txt и переименуем 2.txt в 1.txt, обновим страницу, все предельно просто.
В коде много лишнего и просто страшного. От этого, конечно же, надо избавиться. Я это понимаю, но основной упор в этой заметке не на код ниже строчки, которую вы сейчас дочитываете, а на тот алгоритм, который описан выше.
<?php $t=0; $handle = fopen("1.txt", "r"); $handle2 = fopen("2.txt", "w+"); while (!feof($handle)) { $ar=array(); $line = fgets($handle); $line = substr($line, 1); if ( $line == '' ) { break; } ++$t; $ar=explode('.', $line); $ns=count($ar); array_push($ar, $ns+1); $ns=count($ar); $ar = array_map('trim', $ar); $c=$ns; echo '<br>'; $s=''; foreach($ar as $v) { $s.='.'.$v; } echo $s; fwrite($handle2, "$s\r\n"); while($c !=1) { ++$t; $c--; $cm=$c-1; list($ar[$cm], $ar[$c]) = array($ar[$c], $ar[$cm]); echo '<br>'; $s=''; foreach($ar as $v) { $s.='.'.$v; } echo $s; fwrite($handle2, "$s\r\n"); } } fclose($handle); fclose($handle2); unlink("1.txt"); rename("2.txt", "1.txt"); echo '<br>'.$t; ?> Post Scriptum, ссылки и немного истории.
О нерекурсивном лексикографическом способе (в словарном порядке) генерации перестановок можно посмотреть статьи, раскрывающие смысл алгоритма индийского математика XIV века Нарайаны Пандиты. Видимо, он один из первых составителей нерекурсивного алгоритма.
Методы перестановок можно посмотреть здесь:
study.sfu-kras.ru/DATA/docs/Program…rs/gn_trans.htm
P.P.S
Вдобавок перестановки можно генерировать с помощью псевдослучайных чисел — RANDOM, правда — этого долго, но все же такой способ есть.
И еще один из способов напечатать все перестановки для числа n — сначала сгенерировать все размещения с повторением, а затем удалить значения, в которых символы повторяются — это самый простой для программирования, но самый долгий способ. Его обычно даже не рассматривают, но он все же есть, так как (напомню) перестановки — это частный случай размещений.
ссылка на оригинал статьи http://habrahabr.ru/post/260111/
Добавить комментарий