3 мар 2013 в 01:58

Перебор последовательностей

Ожидает приглашения

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

Задача: перебрать все возможные сочетания букв латинского алфавита, длинной от 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);
}

Данный вариант перебора использовался мною для перебора массива большой вложенности, предварительно модифицирован под конкретную задачу, но принцип оставался тем же.

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

Теги:

Хабы:

Чулан