Алгоритм перебора

Онлайн сервисы > Алгоритм перебора

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

Задача: перебрать все возможные сочетания букв латинского алфавита, длинной от 1 до 3 символов

Решение:

  • На первый взгляд самым простым выходом было бы сделать рекурсивный вызов, в данном частном случае когда идет речь о строках не более 3 симовлов, такое решение будет самое быстрое в реализации, примеров с рекурсией я приводить не стану, но варианты с рекурсией не всегда подходят в меру своего ресурсопотребления.
  • Самым простым вариантом без рекурсии, если задача очень проста и не требует универсальности решения, являются вложенные циклы. Этот вариант прост в реализации, когда речь идет о переборе, например строк длиной не более 2-3 символов, 3 вложенных цикла портят читаемость кода, а если нам нужно не 3 а 30 символов, 30 вложений %)
  • И, наконец, мы дошли до начинки, как можно перебрать все варианты сочетания всех букв, расширим задачу до всех букв с учетом регистра и все цифры (a-zA-Z0-9).
    "Все гениальное - просто", среди читателей этой статьи найдется не мало людей, которым будет достаточно назвать один термин , который лег в основу реализации данного алгоритма, но есть и такие, которым нужно все разжевать, поэтому я приведу код, который это делает на языке програмирования PHP, а термин этот "Системы счисления"
    "Системы счисления" - почти идиально подходят для перебора таких последовательностей, за исключением того, что система счисления воспринимается как число,в результате этого выпадают значения с первым нулевым элементом , т.е если рассматривать десятичную систему счисления, то после 99 идет 100 101 101 ... , а в строковом представлении после 99 должно идти 000 001 002. Ну и, наконец, сам алгоритм:

    // Формируем рабочую систему (a-zA-Z0-9)
    $work = array(0,1,2,3,4,5,6,7,8,9);
    // буквы нижнего регистра
    for($i = 97; $i <= 122; $i++){
        $work[] = chr($i);
    }
    // буквы верхнего регистра
    for($i = 65; $i <= 90; $i++){
        $work[] = chr($i);
    }
    
    // проверим, что получилось, если нужно
    //print_r($work);    
    
    
    // Теперь можно приступать к решению нашего примера 
    // перебор будет в одном цикле, без рекурсии,  и перебирать мы будем не буквы, а цифры
    
    // параметры перебора
    $min_length = 1;
    $max_length = 3; // поставим 3, чтобы хватило памяти для  массива $result
    
    // определяем порядковый номер минимального значения длинной строки $min_length
    $min = str_to_dec(str_repeat($work[sizeof($work)- 1], $min_length-1), $work)+1;
    // определяем порядковый номер максимального значения длинной строки $max_length
    $max = str_to_dec(str_repeat($work[sizeof($work)- 1], $max_length), $work);
    
    // предварительно определить количество возможных значений перебора можно седующим образом
    // столько же итераций совершит цикл
    $size = $max - $min +1;
    
    $result = array();
    for($i = $min; $i <= $max; $i++ )
    {
        $result[] = dec_to_str($i, $work);
    }
    
    // $result = массив, содержащий все возможные значения длинной строки от $min_length до $max_length
    print_r($result);
    
    // для ускорения выполнения всего перебора , цикл от min до max  можно разбить на несколько  циклов
    // и запустить их к примеру с помощью pcntl_fork 
    
    
    #############################################################
    ###                        методы
    #############################################################
    /**
     * переводит строки из системы счисления $work в десятичную систему
     * другими словами находит порядковый номер строки в списке вариаций сочетаний
     * при неизменном массиве $work, каждая последовательность будет иметь свой уникальный порядковый номер 
     * и не будет повторяться
     */
    function str_to_dec($s, $sys)
    {
        $sys = array_flip($sys);
    
        $j = -1;
        $result = 0; 
        for($i = strlen($s)-1; $i >= 0; $i--)
        {
            $j++;
            $result += ($sys[$s[$j]]+1) * pow(sizeof($sys), $i); 
        }
        return $result;
    }
        
    /**
     * переводит число $int (десятичная система) в систему исчисления $work
     */
    function dec_to_str($i, $work)
    {
        $r = sizeof($work);
        $w = '';
        while($i > 0)
        {
            $t = $i % $r;
            if($t == 0){
                $w .= $work[$r-1];
                $i = $i / $r  -1;
            } else {
                $w .= $work[$t-1];
                $i = ($i - $t) / $r;
            }
        }
        return strrev($w);
    }