Generating numbers for lucky tickets

As part of a small test task, it was necessary to implement the old and well-known task with the search for the number of lucky tickets (user-specified digit capacity). Strangely enough, with a large number of sources with a mathematical description of the algorithm , there were few real examples of the implementation of the optimized version (without iteration), but still this part of the task was not a big problem.

In the second part, it was necessary to display the numbers themselves, and here a quick search in the network did not give the expected result. However, the problem is solved, and I would like to share implementations with the habrasoobshchestvo for the sake of obtaining critical opinions and disseminating information for those who may need similar or similar algorithms.

Pro search for the number of lucky tickets

For a start, a few words about the search for the number of lucky numbers (a happy number is understood if the sum of digits on the left side of the number is equal to the sum of digits on the right side of the number (“in Leningrad”)).

Direct search of all possible options could solve the problem if the number of digits in the number was small (4, 6 or 8). However, within the framework of the task, the bit length is set by the user and there are no special restrictions on the number (except logical ones - the number must be even and positive).
')
The optimized algorithm based on mathematics has been described many times, including on habrahabr , therefore I will not bring it fully verbally. The implementation will be shown in the code as two functions. The code is written in 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; } 

The first function takes as a parameter the digit capacity of the number and returns an array similar to the one shown here . In the second function, we run through the array and sum up the squares of the sum of the variants of the combinations:

 /** *          * @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; } 

If the BCMath library is installed on the server with PHP, we use its functions for working with large numbers so that there are no problems with accuracy. Otherwise, if the number is large, the result may be undefined (in practice, with the missing library, it was possible to calculate a maximum for a number with a length of 310 characters).
At the output of the second function, we get the desired result: the number of lucky tickets for the specified number length.

A simple way to generate ticket numbers

Now let's try to display the entire list of the lucky numbers themselves.
First of all, let's look at the simplest algorithm that makes it brute force.

 /** *     ,    * @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; } 

As part of the function, a small optimization has been implemented, with checking the number of found numbers for the amount on the left of the number, which allows reducing the number of iterations in some specific cases.
The algorithm given in this function does a good job when working with numbers up to 8 characters (with paginated output of happy variants of 50 pieces), however, it completely discredits itself on longer numbers, as the number of iterations grows exponentially.

Difficult but fast way to generate ticket numbers

As you can see, from the point of view of mathematics, combinatorics can be used to search for lucky numbers. In search of a suitable algorithm (all the same, in the mathematics itself, knowledge is not so deep as to invent something of its own), after several unsuccessful attempts and constant stumbles on examples with simple enumeration for standard six-digit numbers, it was possible to find an algorithm for generating on the basis of binary logic and decomposition Kruchinina V.V. The existing publication on the topic describes quite well all the mathematics, however, it contains a number of omissions in the description of the implementation algorithm and several annoying errors in the given pseudocode (because of which I had to sit a lot on debugging the implementation).

We describe briefly the main idea. The list of all options consists of the sum of options, in which the digits in one of the parts of the number in the total take values ​​from 0 to n * 9 (where n is the number of characters in half the number). Thus, each variant of a lucky combination of numbers has its own sequence number both within the list of numbers having the same amount, and within the entire list for the selected bit length. As a result, you can choose any lucky option from the entire list by its ordinal number ranging from 1 to k (where k is the total number of lucky tickets for the specified number length). However, it is worth clarifying that, within the framework of this algorithm, tickets selected from 1 to k will not be placed in lexicographical order. If you are interested in the details of the search engine combination search by serial number on the basis of a binary tree, I advise you to carefully read the original source .

So, I have divided the entire implementation into several functions, a couple of which are official for optimizing calculations. It is worth mentioning that the above approach allows you to calculate the number of lucky numbers, however, by itself, it works more slowly than the existing mechanism already described.

 /** *       *   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; } } 

Since this function is called many times with the same parameters, a proxy function was added that caches the result:

 /** @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]; } 

The following function generates a combination by its ordinal number:

 /** *         * @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; } } } 

As in the case with the decompostionCount function, I added a method for caching results and assembling from the resulting array with binary tree traversal data into a combination in decimal form:

 /** @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]; } 

It remains to make on the basis of this base a method for generating the entire lucky number by its common sequence number:

 /** *         * @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; } 

Well, in the end, already a simple method to get a list of lucky tickets:

 /** *        * @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; } 

As a conclusion

The result of all the research can be found here: http://tasks.web-cake.ru/number
For those interested, the entire code based on the Zend Framework is laid out on the github: https://github.com/ShishkinAR/LuckyNumbers
In particular, all the basic algorithms are placed in the model . According to the controller, it is worthwhile to clarify further: the length of the number that the code can handle depends on the server settings. With the presence of the library, the BCMath is mentioned above. In addition, if xdebug is present, it is more careful with the xdebug.max_nesting_level parameter — its default value is 100, which limits recursive passage through the tree and, accordingly, the number of digits in the ticket number. When the server was set up, it was possible to work with numbers over 1000 characters in length. Unfortunately, on the main server, the link above is still limited to 310 characters.

Thanks for attention! I hope the information will be useful and will not be lost in the open spaces of the network and will be available for search to those who may need it.

Comments and criticism are welcome!

Maybe someone has a variant of implementation of the optimized algorithm with getting a list of lucky numbers in their normal lexicographical order?