3

сделаю упрощенный пример, предположим надо подобрать пин код на телефоне, 4 знака от 0 до 9, можно сделать через for

for ($i_1=0; $i_1<=9; $i_1++){
 for ($i_2=0; $i_2<=9; $i_2++){
  for ($i_3=0; $i_3<=9; $i_3++){
   for ($i_4=0; $i_4<=9; $i_4++){
    $pass = $i_1.$i_2.$i_3.$i_4;
   }
  }
 }
}

в итоге $pass выдаст все возможные значения. вопрос есть возможность не писать for в for несколько раз, а как нить по другому. Так как в моем случае это 20 символов, а не 4, и не хочется делать такую конструкцию

1
  • То что вы делаете называется генерация перестановок с повторениями. Это не сложная комбинаторика, да и в интернете легко найти как алгоритм так и реалищацию 20 окт 2017 в 2:26

2 ответа 2

4
function r($pass0, $lvl){
    // Набор допустимых символов
    $sym = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c'];
    if($lvl == 4){
        // Дошли до нужной длины - выводим
        echo $pass0;
    }
    else{
        // Поочерёдно дописываем все допустимые символы в конец строки 
        foreach($sym as $b){
            r($pass0 . $b, $lvl + 1);
        }
    }

}
// Запускаем
r('', 0);
4

предположим надо подобрать пин код на телефоне, 4 знака от 0 до 9, можно сделать через for $dictionary В данном случае всё просто, да и редко нужно больше одного цикла.

for($i=0;$i<=9999;$i++){
  testPin(sprintf('%04d', $i));
}

Но если под вашу задачу не подходит(вы думаете) - полную задачу в студию.

UPD
Поскольку автор уточнил задачу - в словаре для подбора могут быть не только цифры, и он вообще может быть произвольным.

Напрашивается параллель со системами счисления - то есть фактически нам нужно просто в цикле перевести $i из десятичной в N-мерную систему счисления (где N - это длинна словаря), с условием: цифрами в переведённом числе будет сам словарь. Пройти цикл перевода нам нужно столько раз, сколько значений этой системы счисления влезет в заданную длину строки.

Естественно, все математические функции, если не встроены в PHP - то легко ищутся, я нашёл следующую реализацию на SO: https://ru.stackoverflow.com/questions/484607#answer-484666 . Немного модифицировал ф-ю преобразования систем счисления для работы по словарю, и получилось что полный перебор значений строк заданной длинны с заданным словарём реализует следующий алгоритм:

const PIN_LENGTH = 2;
$dictionary = '0129XMVB';
$dictionaryZero = substr($dictionary, 0, 1);

/*Ф-я преобразования из десятичной системы в систему с основанием strlen($dictionary)*/
$entier_from_decimal = function($entier) use ($dictionary, &$entier_from_decimal){
    $base = strlen($dictionary);
    $digit = bcmod($entier, $base);
    $entier = bcdiv($entier, $base);
    if(empty($entier)){
        return $dictionary[$digit];
    }else{
        return $entier_from_decimal($entier, $base) . $dictionary[$digit];
    }
};

/*Ф-я для добавления лидирующих "нулей" */
$pad_entier  = function($either) use($dictionaryZero){
    return str_pad($either, PIN_LENGTH, $dictionaryZero, STR_PAD_LEFT);
};

/* Перебор всех комбинаций символов словаря $dictionary длинны PIN_LENGTH */
for($i=0;$i<pow(strlen($dictionary), PIN_LENGTH);$i++)
{
    echo( $pad_entier($entier_from_decimal($i)) . "\n");
}

Получился очень коротенький алгоритм брутфорса. В примере выведет:

00 01 02 09 0X 0M 0V 0B 10 11 12 19 1X 1M 1V 1B 20 21 22 29 2X 2M 2V 2B 90 91 92 99 9X 9M 9V 9B X0 X1 X2 X9 XX XM XV XB M0 M1 M2 M9 MX MM MV MB V0 V1 V2 V9 VX VM VV VB B0 B1 B2 B9 BX BM BV BB

Спасибо, интересная задача.

3
  • зря наверно сократил так, не подумал что предложат $i<=9999 Полная задача в том, что там и буквы в том числе, а не только цифры от 0 до 9
    – Леха
    20 окт 2017 в 15:01
  • @Леха с буквами не будет слишком отличаться. Ответ дополню позже. 20 окт 2017 в 22:27
  • благодарю за ответ
    – Леха
    28 окт 2017 в 23:01

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.