Текст книги "Гуманитарные основы комбинаторных алгоритмов"

8) Перестановки без формул. (Код PHP)

Перелистывая вопросы и статьи в Интернете, я обратил внимание, что эта простая на первый взгляд тема составляет некую трудность при составлении алгоритма. Попробую максимально просто объяснить себе и вам алгоритм генерации перестановок, вернее, один из возможных. Многие статьи, описывающие тему перестановок, начинаются с формул или теории общей комбинаторики. Отступим от этого канонического принципа.

Есть задача: требуется напечатать все перестановки четырех чисел:

1, 2, 3, 4.

Решение – сначала на листке бумаги

1) Посчитаем последовательно перестановки для одного элемента, для —

1.

Запишем результат:

1

Он равен единице, один элемент переставлять некуда, но мы запомним

результат, пригодится.

2) Посчитаем перестановки для двух элементов – 1 и 2

Запишем результат:

12

21

У нас две перестановки. Все перестановки из дух элементов равны двум. Теперь нужно посчитать для трех элементов – 1, 2, 3. Для этого возьмем наше новое число – 3 и подставим его в каждую строку к перестановкам для двух элементов. Будем подставлять для каждой строки последовательно так, чтобы это число – 3 – побывало на каждой позиции, т. е.: в конце строки, между каждым элементом и в начале строки. Начнем с конца строки. Для первой строки получим результат (в виде квадратной диагональной матрицы):

123

132

312

Для второй строки результат:

213

231

321

Запишем результат.

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.txt построчно.

– Оборвем цикл, если строка пустая.

– Строку будем разбивать и хранить в массиве (explode).

– К ней добавим следующее число (array_push).

Неприятный факт, но еще на каждой итерации самого верхнего цикла будем использовать array_trim, так как в массиве у нас неизвестным образом появляется символ пробела.

– В цикле while будем использовать только list для смещения числа по строке.

– Все результаты будем писать в файл 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, «$srn»);
 
 
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, «$srn»);

}

}

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

Post Post Scriptum

Вдобавок перестановки можно генерировать с помощью псевдослучайных чисел – RANDOM, правда – этого долго, но все же такой способ есть.

– еще один из способов напечатать все перестановки для числа n – сначала сгенерировать все размещения с повторением, а затем удалить значения, в которых символы повторяются – это самый простой для программирования, но самый долгий способ. Его обычно даже не рассматривают, но он все же есть, так как (напомню) перестановки – это частный случай размещений.

Выводы

В результате изучения комбинаторных алгоритмов и размышлений об их применении в современных информационных науках в гуманитарном ключе автор пришёл к выводу, что подобные алгоритмы могут быть использованы:

1) в библиотечных системах, для комбинаторного поиска сочетаний слов в тексте или релевантного поискового вывода.

2) как вспомогательные гипотетические средства при попытках

дешифровки древних (пока неизвестных) алфавитных, слоговых или

созданных клинописью текстов. Эта теория не проверялась на практике, но данный метод явно выводится умозрительно при поверхностном изучении переборной комбинаторики применительно к тексту.

3) для иной работы с языковыми единицами, например, для целей

этимологии – поиска слов (возможно) с одним историческим корнем в одном или даже разных языках.

4) а также для иных целей: порождения и поиска разных сочетаний слов, цветовых сочетаний (схем) и т. д.

5) Возможно, для порождения искусственных языковых единиц.

* В книге используются языки программирования C, C89, PHP.

Дополнение

Ниже алгоритм порождения всех перестановок без

повторений итеративным способом на языке C89,

сокращённый максимально для простоты понимания.

* Заметим, что для внешнего цикла используется

декремент f, что напоминает способ организации

циклов на языке Ассемблера:

#include <stdio. h> </stdio. h>

int main () {

char a [] = «4321»; //array

int i, j;

int f=24;

//factorial

char c;

//buffer

while (f – ) {

printf (»%sn», a);

i=1;

while (a [i]> a [i-1]) i++;

j=0;

while (a [j] <a [i]) j++;

c=a [j];

a [j] =a [i];

a [i] =c;

i – ;

for (j = 0; j <i; i – , j++) {

c = a [i];

a [i] = a [j];

a [j] = c;}}

}