В рамках небольшого тестового задания потребовалось реализовать старую и известную задачу с поиском количества счастливых билетов (указанной пользователем разрядности номера). Как ни странно, при большом числе источников с математическим описанием алгоритма, реальных примеров реализации оптимизированного варианта (без перебора) оказалось немного, но всё же большой проблемы эта часть задания не составила.
Во второй же части потребовалось уже выводить сами номера, и вот тут быстрый поиск в сети ожидаемого результата не дал. Однако, задача решена, и хотелось бы поделиться реализаций с читателим ради получения критического мнения и распространения информации для тех, кому подобные или схожие алгоритмы могут понадобиться.
Про поиск количества счастливых билетов
Для начала пару слов про поиск количества счастливых номеров (под счастливым понимается номер, если сумма цифр в левой части номера равна сумме цифр в правой части номера (“по-ленинградски”)).
Прямым перебором всех возможных вариантов можно было бы решить задачу, если бы количество разрядов в номере было небольшим (4, 6 или 8). Однако в рамках задачи разрядность задаёт пользователь и особых ограничений на номер не накладывается (кроме логичных — число должно быть четным и положительным).
Оптимизированный алгоритм на основе матлогики много раз описывался, в том числе на habrahabr, поэтому полностью его приводить словесно не буду. Реализацию покажем в коде в виде двух функций. Код написан на PHP.
/**
* Расчёт списка возможных вариаций номеров счастливых билетов на основе разрядности
* @param int $iNumber
* @return int[][]
*/
function numberCount($iNumber) {
$iHalf = (int)($iNumber / 2);
$aData = array();
for ($i = 1; $i <= $iHalf; $i++) {
$iLength = $i * 9 + 1;
if ($i == 1) {
for ($j = 0; $j < $iLength; $j++)
$aData[$i][$j] = 1;
}
else {
$iSum = 0;
$k = 0;
for (; $k <= $iLength / 2; $k++) {
$iSum += $aData[$i - 1][$k];
if ($k >= 10)
$iSum -= $aData[$i - 1][$k - 10];
$aData[$i][$k] = $iSum;
}
for (; $k < $iLength; $k++) {
$aData[$i][$k] = $aData[$i][$iLength - 1 - $k];
}
}
}
return $aData;
}
Первая функция принимает в качестве параметра разрядность номера и возвращает массив на подобии приведённого здесь. Во второй функции пробегаем по массиву и суммируем квадраты сумм вариантов комбинаций:
/**
* Быстрый алгоритм расчёта количества счастливых билетов на основе разрядности
* @param int $iNumber
* @return int|string
*/
function countLuckyTicketFast($iNumber) {
$iHalf = (int)($iNumber / 2);
$aData = numberCount($iNumber);
$iCount = 0;
for ($i = 0; $i <= $iHalf * 9; $i++) {
$iCount = function_exists('bcadd') ? bcadd($iCount, bcmul($aData[$iHalf][$i], $aData[$iHalf][$i])) : ($iCount + $aData[$iHalf][$i] * $aData[$iHalf][$i]);
}
return $iCount;
}
Если на сервере с PHP установлена библиотека BCMath — используем её функции для работы с большими числами, чтобы не было проблем с точностью. В ином случае при большой разрядности номера результат может быть неопределён (на практике при отсутствующей библиотеке удавалось рассчитать максимум для номера длиной 310 знаков).
На выходе второй функции получаем желаемый результат: количество счастливых билетов для указанной длины номера.
Простой вариант генерации номеров билетов
Вот теперь попробуем вывести весь список самих счастливых номеров.
В первую очередь посмотрим на простейший алгоритм, который делает это перебором.
/**
* Медленный поиск номеров счастливых билетов, зато по порядку
* @param int $iNumber Разрядность номера
* @param int $iLimit Количество необходимых номеров
* @param int $iStart Первый номер, с которого начинать искать счастливые номера
* @return array
*/
function generateSortedLuckyTicketList($iNumber, $iLimit, $iStart) {
$iHalf = (int) ($iNumber / 2);
$i = 0;
$aNumbersCount = numberCount($iNumber);
$iDelimiter = pow(10, $iHalf);
$iLeft = (int) ($iStart / $iDelimiter);
$iRight = $iStart - $iLeft * $iDelimiter;
$aData = array();
do { // Цикл по левой части номера
$iLeftCount = 0;
$iLeftSum = array_sum(str_split((string)$iLeft));
do { // Цикл по правой части номера
$iRightSum = array_sum(str_split((string)$iRight));
if ($iLeftSum == $iRightSum) {
$iValue = $iLeft * $iDelimiter + $iRight;
$iLength = strlen((string)$iValue);
$aData[] = (string)($iLength == $iNumber ? $iValue : (implode('', array_fill(0, ($iNumber - $iLength), '0')) . $iValue));
$i++;
$iLeftCount++;
// Если количество найденных номеров в правой части для текущей суммы в левой части достигнуто - переходим к следующему числу в левой части
if ($iLeftCount >= $aNumbersCount[$iHalf][$iLeftSum]) {
break;
}
}
$iRight++;
} while ($i < $iLimit && $iRight < $iDelimiter);
$iRight = 1;
$iLeft++;
} while ($i < $iLimit && $iLeft < $iDelimiter);
return $aData;
}
В рамках функции реализована небольшая оптимизация, с проверкой количества найденных номеров для имеющейся в левой части номера суммы, позволяющая сократить количество итераций в некоторых отдельных случаях.
Приведённый в этой функции алгоритм неплохо себя показывает при работе с номерами до 8 знаков (при постраничном выводе счастливых вариантов по 50 штук), однако полностью себя дискредитирует на более длинных номерах, так как количество итераций растёт в геометрической прогрессии.
Сложный, но быстрый вариант генерации номеров билетов
Как можно заметить, с точки зрения математики, для поиска счастливых номеров можно использовать комбинаторику. В поисках подходящего алгоритма (всё же, в самой математике познания не настолько глубоки, чтобы с ходу придумывать что-то своё), после нескольких неудачных попыток и постоянных натыканий на примеры с простым перебором для стандартных шестизначных номеров, удалось найти алгоритм генерации на основе бинарной логики и разложения Кручинина В.В. Имеющаяся публикация на тему неплохо описывает всю математику, однако содержит ряд упущений в описании алгоритма реализации и несколько досадных ошибок в приведённом псевдокоде (из-за которых пришлось немало посидеть над отладкой реализации).
Опишем кратко основную идею. Список всех вариантов состоит из суммы вариантов, в которых цифры в одной из частей номера в сумме принимают значения от 0 до n*9 (где n — количество знаков в половине номера). Таким образом, каждый вариант счастливой комбинации цифр имеет свой порядковый номер как рамках списка чисел, имеющих одинаковую сумму, так и в рамках всего списка для выбранной разрядности. В результате, можно выбрать любой счастливый вариант из всего списка по его порядковому номеру в пределах от 1 до k (где k — общее количество счастливых билетов для указанной длины номера). Однако, стоит уточнить, что, в рамках этого алгоритма, выбираемые последовательно билеты от 1 до k не будут располагаться в лексикографическом порядке. Интересующимся подробностями самого матаппарата поиска комбинации по порядковому номеру на основе бинарного дерева советую всё же внимательно прочитать первоисточник.
Итак, всю реализацию я разделил на несколько функций, пара из которых являются служебными для оптимизации расчётов. Стоит упомянуть, что приведённый подход позволяет рассчитать и количество счастливых номеров, однако сам по себе он работает медленнее, чем уже имеющийся вышеописанный механизм.
/**
* Расчёт количества вариаций для указанных параметров
* Соответствует функции CDecomposition из первоисточника
* @param int $j
* @param int $n
* @param int $m
* @return int
*/
protected function decompositionCount($j, $n, $m) {
if ($m == 0) {
return ($n <= 9) ? 1 : 0;
}
if ($m == $n) {
return 1;
}
if ($j > 0) {
$iRight = $this->decompositionCountProxy($j - 1, $n - 1, $m) + $this->decompositionCountProxy(9, $n - 1, $m - 1);
return $iRight;
} else {
$iLeft = $this->decompositionCountProxy(9, $n - 1, $m - 1);
return $iLeft;
}
}
Так как эта функция много раз вызывается с одинаковыми параметрами, была добавлена прокси-функция, которая кеширует результат:
/** @var int[] Кеш по количеству */
protected $cacheCount = array();
/**
* Прокси-метод для получения количества вариаций для указанных параметров через кеш
* @param int $j
* @param int $n
* @param int $m
* @return int
*/
protected function decompositionCountProxy($j, $n, $m) {
$sKey = $j . '_' . $n . '_' . $m;
if (!isset($this->cacheCount[$sKey])) {
$this->cacheCount[$sKey] = $this->decompositionCount($j, $n, $m);
}
return $this->cacheCount[$sKey];
}
Следующая функция генерирует комбинацию по её порядковому номеру:
/**
* Генерация последовательности по указанными параметрам по номеру последовательности
* @param int[] $v - массив для хранения бинарной последовательности прохода по дереву
* @param int $num - номер счастливого билета
* @param int $j
* @param int $n
* @param int $m
*/
protected function generateDecomposition(&$v, $num, $j, $n, $m) {
if ($m == 0) {
if ($n > 9) return;
for ($i = 1; $i <= $n; $i++) $v[] = 0;
return;
}
if ($m == $n) {
for ($i = 1; $i <= $n; $i++) $v[] = 1;
return;
}
$b = $this->decompositionCountProxy($j - 1, $n - 1, $m);
if ($num <= $b && $j > 0) {
$v[] = 0;
$this->generateDecomposition($v, $num, $j - 1, $n - 1, $m);
} else {
$v[] = 1;
if ($j == 0) {
$this->generateDecomposition($v, $num, $j, $n - 1, $m - 1);
} else {
$this->generateDecomposition($v, $num - $b, 9, $n - 1, $m - 1);
return;
}
}
}
Как в случае и с функцией decompostionCount, добавил метод для кеширования результатов и сборки из полученного массива с бинарными данными обхода дерева в комбинацию в десятичном виде:
/** @var string[] Кеш по значению */
protected $cacheValue = array();
/**
* Прокси-метод для получения варианта декомпозиции для указанных параметров по номеру через кеш
* @param int $num номер декомпозиции
* @param int $j
* @param int $n
* @param int $m
* @return string
*/
protected function generateDecompositionProxy($num, $j, $n, $m) {
$sKey = $num . '_' . $j . '_' . $n . '_' . $m;
if (!isset($this->cacheValue[$sKey])) {
$v = array();
$this->generateDecomposition($v, $num, $j, $n, $m);
$r = array();
$s = 0; $c = 0;
foreach (array_reverse($v) as $i) {
if ($i == 0) {
$c++;
} else {
$r[] = $c;
$c = 0; $s++;
}
}
$r[] = $c;
$this->cacheValue[$sKey] = implode('', $r);
}
return $this->cacheValue[$sKey];
}
Осталось на основе этой базы сделать метод для генерации всего счастливого номера по его общему порядковому номеру:
/**
* Генерация номера счастливого билета по его порядковому номеру
* @param int $iNumber - количество разрядов
* @param int $iNum - порядковый номер
* @return string
*/
public function generateLuckyTicket($iNumber, $iNum) {
$iHalf = (int)($iNumber / 2);
$iLength = (int)($iHalf * 9);
$b = 1;
// Уточнение порядкового номера в рамках конкретной группы по сумме цифр в половине номера
for ($i = 0; $i <= $iLength; $i++) {
if ($i <= ($iLength / 2)) {
$b = $this->decompositionCountProxy(9, $i + $iHalf - 1, $iHalf - 1);
} else {
$b = $this->decompositionCountProxy(9, $iLength - $i + $iHalf - 1, $iHalf - 1);
}
if (($iNum - pow($b, 2)) < 0) break;
$iNum -= pow($b, 2);
}
$iNumLeft = (int)($iNum / $b);
$iNumRight = $iNum % $b;
// Получение декомпозиций по найденному номеру для левой и для правой части
$sLeft = $this->generateDecompositionProxy($iNumLeft + 1, 9, $i + $iHalf - 1, $iHalf - 1);
$sRight = $this->generateDecompositionProxy($iNumRight + 1, 9, $i + $iHalf - 1, $iHalf - 1);
$iLeftLength = strlen($sLeft);
$iRightLength = strlen($sRight);
$sLeft = ($iLeftLength == $iHalf) ? $sLeft : (array_fill(0, $iHalf - $iLeftLength, '0'));
$sRight = ($iRightLength == $iHalf) ? $sRight : (array_fill(0, $iHalf - $iRightLength, '0'));
return $sLeft . $sRight;
}
Ну и, в конце концов, уже простой метод для получения списка счастливых билетов:
/**
* Постраничная генерация номеров счастливых билетов указанной разрядности
* @param int $iNumber
* @param int $iPage
* @param int $iLimit
* @return string[]
*/
public function generateLuckyTicketList($iNumber, $iPage, $iLimit) {
$iMax = $this->countLuckyTicket($iNumber);
$iOffset = $iLimit * ($iPage - 1);
$aData = array();
for ($i = $iOffset; $i < min($iMax, $iOffset + $iLimit); $i++) {
$iValue = $this->generateLuckyTicket($iNumber, $i);
$aData[] = $iValue;
}
return $aData;
}
В качестве заключения
Результат всех изысканий можно посмотреть тут: http://tasks.web-cake.ru/number
Для интересующихся, весь код на основе Zend Framework выложен на гитхабе: https://github.com/ShishkinAR/LuckyNumbers
В частности, все основные алгоритмы помещены в модель. По контроллеру стоит дополнительно уточнить: длина номера, которую может обработать код, зависит от настроек сервера. При наличие библиотеки BCMath упоминалось выше. Кроме того, при наличие xdebug стоит осторожнее с параметром xdebug.max_nesting_level — по-умолчанию его значение равно 100, что ограничивает рекурсивное прохождение по дереву и, соответственно, количество разрядов в номере билета. При донастройке сервера получалось работать с числами длиной свыше 1000 знаков. К сожалению, на основном сервере по ссылке выше пока стоит ограничение в 310 знаков.
Спасибо за внимание! Надеюсь, информация будет полезной и не затеряется на просторах сети и будет доступна для поиска тем, кому это может потребоваться.
Комментария и критика приветствуются!
Возможно, у кого-то есть вариант реализации оптимизированного алгоритма с получением списка счастливых номеров в их нормальном лексикографическом порядке?
Автор: VangerAsh
