Форумы портала PHP.SU :: Версия для печати :: Перестановки алфавита без рекурсии. Без массивов. PHP

1. dcc0 - 06 Сентября, 2014 - 17:05:11 - перейти к сообщению

Ребята, если кому-то будет интересна эта тема, вот мои наработки.
Пока, вроде, получилось. Правда, есть ограничение на генерируемые размещения.
Собственно, заметка о том, как превратить размещения в перестановки.

Все алгоритмы, которые я встречал в Интернете на ключевые слова "перестановки и permutations" мне показались сложными для понимания. Заодно отталкивает использование рекурсии. Работая над другим скриптом, пришел к следующему выводу.
Чтобы получить все перестановки, которые, как известно, равны факториалу n!,
сначала надо получить все размещения с повторениями. Мной был найден такой скрипт и несколько переделан, взят с hashcode, автора не помню.
Мы генерируем все размещения в данном случае 4-х элементов - abcd. Для этого используется цикл до 4 в степени 4 (все размещения с повторением). Данные преобразуются в четверичную систему, дописываются нули слева. Затем с помощью strtr преобразование в abcd. Вот, с первым скриптом все.

PHP:
скопировать код в буфер обмена

<?PHP 
/*Cоздать файл с набором алфавита. Исходный скрипта взят с hashcode*/
 $handle = fopen("f.txt", "w");
$a=-1;
while(++$a<256) {
   $c=str_pad(base_convert($a, 10, 4), 4, "0", STR_PAD_LEFT);
 $b=strtr($c, "0123", "abcd");
fwrite($handle, "$b\r\n");       
}
 fclose($handle);
 ?>
 

А дальше?! Надо удалить из всех размещений каждую строку, в который символ повторяется. Второй скрипт читает из файла f.txt построчно, проверяет количество одного символа в строке и записывает в промежуточный файл только те строки, в которых символ один. Когда цикл переберет все записи на одну букву, подставит другую. Первый цикл - перебора массива - будет иметь столько итераций, сколько всего букв в алфавите, т.е. n. Иначе говоря, есть abcd - 4 буквы, у цикла перебора массива будет 4 итерации.
Промежуточные вычисления записываются в дополнительный файлы, потом файлы удаляются и переименовываются.

PHP:
скопировать код в буфер обмена

 
<?PHP 
/*Входной алфавит*/
 $arr = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h');
 
/*Количество символов*/
$n=3;
/*Перебор. Сброс на последнем символе*/
foreach($arr as $k => $v) {
    if($k==$n) {
  break;
 }
 $handle = fopen("f.txt", "r");
    $handl1 = fopen("f1.txt", "w");
 /*Читаем из файла по строчно*/         
while (!feof($handle)) {
  $buffer = fgets($handle);
  
   /*Если символ встречается 1 раз пишем в другой файл. Переменная - шаблон 
   подставляется из цикла сверху*/      
$c = preg_match_all("/$v{1}/",  $buffer, $out);
if($c==1) {
fwrite($handl1, "$buffer");
 }
}
 fclose($handle);
fclose($handl1);
/*Переименовываем все файлы, удалем промежуточные*/
 rename("f.txt", "old1_f.txt");
  unlink ("old1_f.txt");
rename("f1.txt", "f.txt");
} 
$c=file('f.txt');
print_r($c);
?> 
 