- PVSM.RU - https://www.pvsm.ru -
В рамках небольшого тестового задания потребовалось реализовать старую и известную задачу с поиском количества счастливых билетов [1] (указанной пользователем разрядности номера). Как ни странно, при большом числе источников с математическим описанием алгоритма [2], реальных примеров реализации оптимизированного варианта (без перебора) оказалось немного, но всё же большой проблемы эта часть задания не составила.
Во второй же части потребовалось уже выводить сами номера, и вот тут быстрый поиск в сети ожидаемого результата не дал. Однако, задача решена, и хотелось бы поделиться реализаций с читателим ради получения критического мнения и распространения информации для тех, кому подобные или схожие алгоритмы могут понадобиться.
Для начала пару слов про поиск количества счастливых номеров (под счастливым понимается номер, если сумма цифр в левой части номера равна сумме цифр в правой части номера (“по-ленинградски”)).
Прямым перебором всех возможных вариантов можно было бы решить задачу, если бы количество разрядов в номере было небольшим (4, 6 или 8). Однако в рамках задачи разрядность задаёт пользователь и особых ограничений на номер не накладывается (кроме логичных — число должно быть четным и положительным).
Оптимизированный алгоритм на основе матлогики много раз описывался [3], в том числе на habrahabr [4], поэтому полностью его приводить словесно не буду. Реализацию покажем в коде в виде двух функций. Код написан на 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;
}
Первая функция принимает в качестве параметра разрядность номера и возвращает массив на подобии приведённого здесь [3]. Во второй функции пробегаем по массиву и суммируем квадраты сумм вариантов комбинаций:
/**
* Быстрый алгоритм расчёта количества счастливых билетов на основе разрядности
* @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 [5] — используем её функции для работы с большими числами, чтобы не было проблем с точностью. В ином случае при большой разрядности номера результат может быть неопределён (на практике при отсутствующей библиотеке удавалось рассчитать максимум для номера длиной 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 штук), однако полностью себя дискредитирует на более длинных номерах, так как количество итераций растёт в геометрической прогрессии.
Как можно заметить, с точки зрения математики, для поиска счастливых номеров можно использовать комбинаторику. В поисках подходящего алгоритма (всё же, в самой математике познания не настолько глубоки, чтобы с ходу придумывать что-то своё), после нескольких неудачных попыток и постоянных натыканий на примеры с простым перебором для стандартных шестизначных номеров, удалось найти алгоритм генерации на основе бинарной логики и разложения Кручинина В.В. [6] Имеющаяся публикация [7] на тему неплохо описывает всю математику, однако содержит ряд упущений в описании алгоритма реализации и несколько досадных ошибок в приведённом псевдокоде (из-за которых пришлось немало посидеть над отладкой реализации).
Опишем кратко основную идею. Список всех вариантов состоит из суммы вариантов, в которых цифры в одной из частей номера в сумме принимают значения от 0 до n*9 (где n — количество знаков в половине номера). Таким образом, каждый вариант счастливой комбинации цифр имеет свой порядковый номер как рамках списка чисел, имеющих одинаковую сумму, так и в рамках всего списка для выбранной разрядности. В результате, можно выбрать любой счастливый вариант из всего списка по его порядковому номеру в пределах от 1 до k (где k — общее количество счастливых билетов для указанной длины номера). Однако, стоит уточнить, что, в рамках этого алгоритма, выбираемые последовательно билеты от 1 до k не будут располагаться в лексикографическом [8]порядке. Интересующимся подробностями самого матаппарата поиска комбинации по порядковому номеру на основе бинарного дерева советую всё же внимательно прочитать первоисточник [7].
Итак, всю реализацию я разделил на несколько функций, пара из которых являются служебными для оптимизации расчётов. Стоит упомянуть, что приведённый подход позволяет рассчитать и количество счастливых номеров, однако сам по себе он работает медленнее, чем уже имеющийся вышеописанный механизм.
/**
* Расчёт количества вариаций для указанных параметров
* Соответствует функции 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 [9]
Для интересующихся, весь код на основе Zend Framework выложен на гитхабе: https://github.com/ShishkinAR/LuckyNumbers [10]
В частности, все основные алгоритмы помещены в модель [11]. По контроллеру [12]стоит дополнительно уточнить: длина номера, которую может обработать код, зависит от настроек сервера. При наличие библиотеки BCMath упоминалось выше. Кроме того, при наличие xdebug стоит осторожнее с параметром xdebug.max_nesting_level — по-умолчанию его значение равно 100, что ограничивает рекурсивное прохождение по дереву и, соответственно, количество разрядов в номере билета. При донастройке сервера получалось работать с числами длиной свыше 1000 знаков. К сожалению, на основном сервере по ссылке выше пока стоит ограничение в 310 знаков.
Спасибо за внимание! Надеюсь, информация будет полезной и не затеряется на просторах сети и будет доступна для поиска тем, кому это может потребоваться.
Комментария и критика приветствуются!
Возможно, у кого-то есть вариант реализации оптимизированного алгоритма с получением списка счастливых номеров в их нормальном лексикографическом порядке?
Автор: VangerAsh
Источник [13]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/40868
Ссылки в тексте:
[1] счастливых билетов: http://ru.wikipedia.org/wiki/%D0%A1%D1%87%D0%B0%D1%81%D1%82%D0%BB%D0%B8%D0%B2%D1%8B%D0%B9_%D0%B1%D0%B8%D0%BB%D0%B5%D1%82
[2] математическим описанием алгоритма: http://www.ega-math.narod.ru/Quant/Tickets.htm
[3] описывался: http://www.ega-math.narod.ru/Quant/Tickets.htm#A2
[4] habrahabr: http://habrahabr.ru/post/13235/
[5] BCMath: http://php.net/manual/ru/book.bc.php
[6] Кручинина В.В.: http://www.tusur.ru/ru/faculties/fsu/mathematics/chief.html
[7] публикация: http://window.edu.ru/resource/295/37295/files/2005_1_39-44.pdf
[8] лексикографическом : http://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BA%D1%81%D0%B8%D0%BA%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D0%BA
[9] http://tasks.web-cake.ru/number: http://tasks.web-cake.ru/number
[10] https://github.com/ShishkinAR/LuckyNumbers: https://github.com/ShishkinAR/LuckyNumbers
[11] модель: https://github.com/ShishkinAR/LuckyNumbers/blob/master/application/modules/number/models/Numbers.php
[12] контроллеру : https://github.com/ShishkinAR/LuckyNumbers/blob/master/application/modules/number/controllers/ApiController.php
[13] Источник: http://habrahabr.ru/post/189982/
Нажмите здесь для печати.