PHP.SU

Программирование на PHP, MySQL и другие веб-технологии

PHP.SU Портал

Главная

Помощь

Поиск

Поиск Яндекс Вакансии

Пользователи

Здравствуйте, Гость

( Вход · Регистрация · Правила форума )

Забыли пароль?

Перестановки алфавита без рекурсии. Без массивов. PHP

Форумы портала PHP.SU » PHP » Программирование на PHP » Хранение данных, их вывод и обработка (Модераторы: OrmaJever, Саныч)

Страниц (1): [1]

Описание: перестановки php permutations

Поиск в теме | Версия для печати

dcc0	Отправлено: 06 Сентября, 2014 - 17:05:11
Участник Покинул форум Сообщений всего: 1043 Дата рег-ции: Июль 2014 Помог: 10 раз(а)	Ребята, если кому-то будет интересна эта тема, вот мои наработки. Пока, вроде, получилось. Правда, есть ограничение на генерируемые размещения. Собственно, заметка о том, как превратить размещения в перестановки. Все алгоритмы, которые я встречал в Интернете на ключевые слова "перестановки и 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); ?> (Отредактировано автором: 09 Июня, 2015 - 11:43:26) ----- Март 2021. Бросил программирование

dcc0	Отправлено: 07 Сентября, 2014 - 19:35:06
Участник Покинул форум Сообщений всего: 1043 Дата рег-ции: Июль 2014 Помог: 10 раз(а)	Еще такой вариант получения перестановок, полуавтоматический. Не знаю, где может пригодиться. Идея такая: можно генерировать любой набор букв рандомно. Например, при помощи скрипта из этой статьи: http://www.php.su/articles/?cat=...les&page=052 Писать этот набор в файл, другим скриптом отсеивать все строчки, в которых 1 буква встречается более одного раза, а затем применять arrar_unique для поиска уникальных. Таким образом поиск будет постепенным. Спойлер (Отобразить) PHP: скопировать код в буфер обмена <form method=post> <input type=text name=number value="3"> <input type=submit value="Генерировать"> <form><br><br> <?PHP // Параметр $number - сообщает число // символов в пароле function gen($i) { $number=5; $arr = array('a','b','c','d','e'); // Генерируем пароль $pass = ""; for($c = 0; $c < $number; $c++) { // Вычисляем случайный индекс массива $index = rand(0, count($arr) - 1); $pass .= $arr[$index]; } $handle = fopen("f.txt", "a"); fwrite($handle, "$pass\r\n"); fclose($handle); ++$i; if ($i==500) { exit; } gen($i); } $i=0;; gen($i); ?> Спойлер (Отобразить) PHP: скопировать код в буфер обмена <?PHP /Входной алфавит/ $arr = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'); /Количество символов/ $n=4; /Перебор. Сброс на последнем символе/ 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'); $l=array_unique($c); print_r($l); echo count($l); ?> ----- Март 2021. Бросил программирование

nkl	Отправлено: 08 Сентября, 2014 - 10:40:31
Посетитель Покинул форум Сообщений всего: 305 Дата рег-ции: Янв. 2012 Помог: 1 раз(а)	Это для чего вообще?

Tyoma5891	Отправлено: 08 Сентября, 2014 - 11:02:33
Частый посетитель Покинул форум Сообщений всего: 621 Дата рег-ции: Авг. 2013 Помог: 5 раз(а)	nkl пишет: Это для чего вообще? у меня такое подозрение, для побора паролей, но для этого достаточно тупого перебора методом +1 )

dcc0	Отправлено: 08 Сентября, 2014 - 11:09:13
Участник Покинул форум Сообщений всего: 1043 Дата рег-ции: Июль 2014 Помог: 10 раз(а)	nkl, практического применения пока не вижу, но интересны способы получения всех перестановок алфавита, например, abcd или ab02 или a+?& и т.д. Наиболее оптимальным считается рекурсивный алгоритм. Пример 1: http://stackoverflow[dot]com/questio[dot][dot][dot]tations-in-a-set Пример 2: http://tvolf[dot]blogspot[dot]ru/2013/09/php[dot]html С хорошим объяснением. Но для понимания довольно сложен (мое мнение). Рекурсивный будет работать с символами до 10, потом просто не хватит памяти (хотя тут зависит от машины и настроек). Второй вариант без рекурсии, где сначала надо найти все размещения с повторениями, сгенерирует до 7 включительно, так как понятно разм. с повторениями намного больше. Пример, если всех перестановок семи элементов abcdefg - 7! = 5040, то размещений 7⁷ = 823543. Т.е. вариант долгий и нудный, но он есть. Вариант третий можно автоматизировать, он совсем долгий (почти бесконечный ) Один скрипт генерирует n-ое количество случайных выборок и сохраняет в файл, другой скрипт забирает результат удаляет то - что не попадает под перестановку, например aaabc, потом удаляет повторы, опять же можно сохранять в другой файл, который будет базой Третий скрипт находит все перестановки 4 эл. за 100 рекурсивных вызовов. (Добавление) Tyoma5891 пишет: у меня такое подозрение, для побора паролей, но для этого достаточно тупого перебора методом +1 ) Причем тут перестановки и перебор? При перестановках вы не получаете перебора всех значений. Третий вариант интересен тем, что последовательность перестановок будет случайной. (Отредактировано автором: 08 Сентября, 2014 - 14:37:15) ----- Март 2021. Бросил программирование

Поиск в теме | Версия для печати

Страниц (1): [1]

Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)

« Хранение данных, их вывод и обработка »

Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.