Перелистывая вопросы и статьи в Интернете, я обратил внимание, что эта простая на первый взгляд тема составляет некую трудность при составлении алгоритма. Попробую максимально просто объяснить себе и вам алгоритм генерации перестановок, вернее, один из возможных.
Многие статьи, описывающие тему перестановок, начинаются с формул или теории общей комбинаторики. Отступим от этого канонического принципа.
Есть задача: требуется напечатать все перестановки четырех чисел:
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 для каждой строки в конце, между каждым элементом и в начале строки.
Снова начнем с конца:
Получим 24 перестановки. Легко проверить — факториал числа 4 равен 24:
4! = 1*2*3*4=24
Обратим еще раз внимание: мы берем результаты, найденные на предыдущем шаге, берем число выше на единицу, подставляем это число в каждую строку — тянем с конца строки в начало. Когда это число на первой позиции, мы берем следующую строку и повторяем действия. Получаем простой алгоритм перестановок в нелексикографическом порядке, который можно быстро перевести на машинный язык. Результат, кстати, сильно напоминает код Грея для перестановок, а также алгоритм Джонсона-Троттера. Хотя я не вникал сильно, но если интересно, то почитать о нем можно, набрав в поисковике «Коды Грея для перестановок».
Об авторском праве
Кстати, лично мне протягивание цифры по строке пришло в голову после одной ассоциации из жизни, эта ассоциация связана с плетением лаптей или корзинок, когда каждое новое кольцо образуется протягиванием лыка или ивового прутика через каждую вертикальную дугу.
Закрепим все это вот такой последовательностью картинок:
А теперь попробуем реализовать этот алгоритм на PHP, для хранения значений будем использовать файлы. Создадим два файла с именами 1.txt и 2.txt, в файл 1.txt запишем единицу.
Для каких-то практических задач использование нижеприведенного когда не планируется, поэтому навернем в нем всего побольше:
1. Будем читать файл 1.txt построчно.
3. Оборвем цикл, если строка пустая.
4. Строку будем разбивать и хранить в массиве (explode).
5. К ней добавим следующее число (array_push).
Неприятный факт, но еще на каждой итерации самого верхнего цикла будем использовать array_trim, так как в массиве у нас неизвестным образом появляется символ проблела.
6. В цикле while будем использовать только list для смещения числа по строке.
7. Все результаты будем писать в файл 2.txt, затем удалим 1.txt и переименуем 2.txt в 1.txt, обновим страницу, все предельно просто.
Основной упор в этой заметке не на код ниже строчки, которую вы сейчас дочитываете, а на тот алгоритм, который описан выше.
Post Scriptum, ссылки и немного истории.
О нерекурсивном лексикографическом способе (в словарном порядке) генерации перестановок можно посмотреть статьи, раскрывающие смысл алгоритма индийского математика XIV века Нарайаны Пандиты. Видимо, он один из первых составителей нерекурсивного алгоритма.
Об истории комбинаторики в разных странах:
www.williamspublishing.com/PDF/978-5-8459-1158-2/part.pdf
Методы перестановок можно посмотреть здесь:
study.sfu-kras.ru/DATA/docs/Program...rs/gn_trans.htm
Для изучения вопроса о перестановках на php хотел бы отметить вот эту статью товарища tvolf, очень пригодилась (Спасибо огромное):
tvolf.blogspot.ru/2013/09/php.html
P.P.S
Вдобавок перестановки можно генерировать с помощью псевдослучайных чисел — RANDOM, правда — этого долго, но все же такой способ есть.
И еще один из способов напечатать все перестановки для числа n — сначала сгенерировать все размещения с повторением, а затем удалить значения, в которых символы повторяются — это самый простой для программирования, но самый долгий способ. Его обычно даже не рассматривают, но он все же есть, так как (напомню) перестановки — это частный случай размещений.
Многие статьи, описывающие тему перестановок, начинаются с формул или теории общей комбинаторики. Отступим от этого канонического принципа.
Есть задача: требуется напечатать все перестановки четырех чисел:
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 3 2 4> <3 1 2 4> <2 1 3 4> <2 3 1 4> <3 2 1 4>
<1 2 4 3> <1 3 4 2> <3 1 4 2> <2 1 4 3> <2 3 4 1> <3 2 4 1>
<1 4 2 3> <1 4 3 2> <3 4 1 2> <2 4 1 3> <2 4 3 1> <3 4 2 1>
<4 1 2 3> <4 1 3 2> <4 3 1 2> <4 2 1 3> <4 2 3 1> <4 3 2 1>
Получим 24 перестановки. Легко проверить — факториал числа 4 равен 24:
4! = 1*2*3*4=24
Обратим еще раз внимание: мы берем результаты, найденные на предыдущем шаге, берем число выше на единицу, подставляем это число в каждую строку — тянем с конца строки в начало. Когда это число на первой позиции, мы берем следующую строку и повторяем действия. Получаем простой алгоритм перестановок в нелексикографическом порядке, который можно быстро перевести на машинный язык. Результат, кстати, сильно напоминает код Грея для перестановок, а также алгоритм Джонсона-Троттера. Хотя я не вникал сильно, но если интересно, то почитать о нем можно, набрав в поисковике «Коды Грея для перестановок».
Об авторском праве
Кстати, лично мне протягивание цифры по строке пришло в голову после одной ассоциации из жизни, эта ассоциация связана с плетением лаптей или корзинок, когда каждое новое кольцо образуется протягиванием лыка или ивового прутика через каждую вертикальную дугу.
Закрепим все это вот такой последовательностью картинок:
А теперь попробуем реализовать этот алгоритм на PHP, для хранения значений будем использовать файлы. Создадим два файла с именами 1.txt и 2.txt, в файл 1.txt запишем единицу.
Для каких-то практических задач использование нижеприведенного когда не планируется, поэтому навернем в нем всего побольше:
1. Будем читать файл 1.txt построчно.
3. Оборвем цикл, если строка пустая.
4. Строку будем разбивать и хранить в массиве (explode).
5. К ней добавим следующее число (array_push).
Неприятный факт, но еще на каждой итерации самого верхнего цикла будем использовать array_trim, так как в массиве у нас неизвестным образом появляется символ проблела.
6. В цикле while будем использовать только list для смещения числа по строке.
7. Все результаты будем писать в файл 2.txt, затем удалим 1.txt и переименуем 2.txt в 1.txt, обновим страницу, все предельно просто.
Основной упор в этой заметке не на код ниже строчки, которую вы сейчас дочитываете, а на тот алгоритм, который описан выше.
<?php
$handle = fopen("1.txt", "r");
$handle2 = fopen("2.txt", "w+");
while (!feof($handle))
{
$ar = array();
$line = fgets($handle);
if ($line == '')
{
break;
}
$ar = explode('.', $line);
$c = count($ar);
array_push($ar, $c + 1);
$c+= 1;
$ar = array_map('trim', $ar);
echo '<br />';
$s = implode('.', $ar);
echo $s;
fwrite($handle2, "$s\r\n");
while ($c != 1)
{
$c--;
list($ar[$c-1], $ar[$c]) = array(
$ar[$c],
$ar[$c-1]
);
echo '<br />';
$s = implode('.', $ar);
echo $s;
fwrite($handle2, "$s\r\n");
}
}
fclose($handle);
fclose($handle2);
unlink("1.txt");
rename("2.txt", "1.txt");
?>
Post Scriptum, ссылки и немного истории.
О нерекурсивном лексикографическом способе (в словарном порядке) генерации перестановок можно посмотреть статьи, раскрывающие смысл алгоритма индийского математика XIV века Нарайаны Пандиты. Видимо, он один из первых составителей нерекурсивного алгоритма.
Об истории комбинаторики в разных странах:
www.williamspublishing.com/PDF/978-5-8459-1158-2/part.pdf
Методы перестановок можно посмотреть здесь:
study.sfu-kras.ru/DATA/docs/Program...rs/gn_trans.htm
Для изучения вопроса о перестановках на php хотел бы отметить вот эту статью товарища tvolf, очень пригодилась (Спасибо огромное):
tvolf.blogspot.ru/2013/09/php.html
P.P.S
Вдобавок перестановки можно генерировать с помощью псевдослучайных чисел — RANDOM, правда — этого долго, но все же такой способ есть.
И еще один из способов напечатать все перестановки для числа n — сначала сгенерировать все размещения с повторением, а затем удалить значения, в которых символы повторяются — это самый простой для программирования, но самый долгий способ. Его обычно даже не рассматривают, но он все же есть, так как (напомню) перестановки — это частный случай размещений.
