小さなテストタスクの一環として、 ハッピーチケットの数（ユーザー指定のビット数）を見つけることで、古くてよく知られているタスクを実装する必要がありました。 奇妙なことに、 アルゴリズムの数学的な説明を含む多数のソースがあるため、最適化されたバージョンの実装の実際の例はほとんどありませんが、タスクのこの部分は大きな問題ではありませんでした。
2番目の部分では、既に数字自体を表示する必要がありましたが、ここではネットワークをすばやく検索しても期待した結果が得られませんでした。 ただし、問題は解決されています。同様のアルゴリズムまたは類似のアルゴリズムを必要とする可能性のある人々のために批判的な意見を入手し、情報を広めるために、実装をhabrasocietyと共有したいと思います。
ラッキーチケットの数の確認について
まず、幸運な数字の数を見つけることについてのいくつかの言葉（幸運は、数字の左側の数字の合計が数字の右側の数字の合計に等しい場合の数字を意味します（「レニングラードで」））。
部屋のビット数が少ない場合（4、6、または8）、すべての可能なオプションを直接列挙することで問題を解決できます。 ただし、タスクの一部として、ビット数はユーザーによって設定され、数に特別な制限はありません（論理的なものを除く-数は偶数で正でなければなりません）。
habrahabrを含め、ロジックに基づいて最適化されたアルゴリズムは何度も説明されているため、完全に口頭で説明することはしません。 コード内の実装を2つの関数の形式で示します。 コードは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; }
最初の関数はパラメータとして数値のビット深度を取り、 ここで与えられたものと同様の配列を返します。 2番目の関数では、配列を調べて、組み合わせの合計の2乗を要約します。
/** * * @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; }
BCMathライブラリがPHPを搭載したサーバーにインストールされている場合、その関数を使用して多数の数値を処理するため、精度に問題はありません。 そうでない場合、数字の桁数が大きいと、結果が不定になる可能性があります（実際には、ライブラリが欠落しているため、310文字の長さの数字の最大値を計算できました）。
2番目の関数の出力で、目的の結果、つまり指定された数の長さのラッキーチケットの数を取得します。
チケット番号を生成する簡単な方法
では、ラッキーナンバーのリスト全体を表示してみましょう。
まず最初に、このやり過ぎを引き起こす最も単純なアルゴリズムを見てみましょう。
/** * , * @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桁の数字の単純な列挙による絶え間ない遭遇の後、バイナリベースの生成アルゴリズムを見つけることができましたロジックと分解Kruchinina VV このトピックに関する既存の出版物は数学全体をうまく説明していますが、実装アルゴリズムの説明にいくつかの省略があり、特定の擬似コードにいくつかの迷惑なエラーが含まれています（そのため、実装のデバッグに多くの時間を費やさなければなりませんでした）。
主なアイデアを簡単に説明しましょう。 すべてのオプションのリストは、オプションの合計で構成されます。このオプションでは、合計数のいずれかの部分の数値が0〜n * 9（nは数値の半分の文字数）の値を取ります。 したがって、数字の幸せな組み合わせの各バリアントには、同じ量の数字のリスト内と、選択したビット深度のリスト全体の両方に、独自のシリアル番号があります。 その結果、1からkの範囲のシリアル番号でリスト全体から任意のラッキーオプションを選択できます（kは指定された番号の長さのラッキーチケットの総数です）。 ただし、このアルゴリズムのフレームワーク内で、1からkまで連続して選択されたチケットは辞書編集順に並べられないことを明確にする価値があります。 バイナリツリーに基づくシリアル番号による検索装置の組み合わせの詳細に興味がある人は、それでもソースを注意深く読むことをお勧めします。
そのため、実装全体をいくつかの関数に分割しました。そのうちの2つは、計算を最適化する公式の関数です。 上記のアプローチではラッキーナンバーの数を計算できますが、それ自体ではすでに説明したメカニズムよりも動作が遅いことに言及する価値があります。
/** * * 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関数と同様に、結果をキャッシュし、バイナリツリートラバースデータを含む結果の配列から10進数の組み合わせにアセンブルするためのメソッドを追加しました。
/** @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に基づくすべてのコードがgithubで入手できます： https : //github.com/ShishkinAR/LuckyNumbers
特に、すべての基本的なアルゴリズムはモデルに配置されます。 コントローラーはさらに明確にする必要があります。コードが処理できる数値の長さは、サーバーの設定によって異なります。 上記のBCMathライブラリの存在。 さらに、xdebugがある場合は、xdebug.max_nesting_levelパラメーターに注意する必要があります-デフォルトでは、その値は100です。これにより、ツリーを再帰的に通過し、それに応じてチケット番号のビット数が制限されます。 サーバーを再構成すると、1000文字を超える数で動作することが判明しました。 残念ながら、メインサーバーでは、上記のリンクにはまだ310文字の制限があります。
ご清聴ありがとうございました！ 情報が有用であり、ネットワークのオープンスペースで迷子にならず、それを必要とする人が検索できるようになることを願っています。
コメントと批判を歓迎します！
おそらく誰かが最適化されたアルゴリズムを実装して、通常の辞書式順序でラッキーナンバーのリストを取得するオプションを持っているでしょうか？