File: Calculus.php

<?php

/**
 * Copyright (C) 2011+ Martin Lacroix
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * @license GNU General Public License Version 3 (GPLv3)
 * @link http://www.gnu.org/licenses/
 */

/**
 * PHP_VER   : 5.3+
 * LIBRARIES : BCMATH
 * KEYWORDS  : NUMBER DISTINCT UNIQUE DIGIT RANGE LIMIT LEADING ZERO
 *             NOMBRE DISTINCT UNIQUE DIGIT CHIFFRE BORNE LIMITE ZERO SIGNIFICATIF
 *
 * Class mainly computing the number of numbers with unique digits over a range.
 * Include the option of leading zero
 *
 * Classe en charge principalement du calcul du nombre de nombres
 * constitués de digits uniques qu'il est possible de créer entre deux limites
 * Gère l'option des zéros significatifs du début
 *
 * @package tools
 * @version 1.0.1
 * @author Martin Lacroix
 */
class Calculus {

   const GREATEST_NUMBER_WITH_UNIQUE_DIGITS = '9876543210';

   /**
    * Calcule et renvoie le nombre de nombres constitués uniquement de digits uniques
    * qu'il est possible de créer entre deux limites
    * Si les zéros du début sont significatifs alors la limite ayant la longueur la plus courte
    * sera complétée par des 0 afin d'atteindre la longueur de la limite la plus longue
    * Ex : si min = 000000 et max = 999 => $max = 000999
    * @param mixed $min Tout entier positif ou nul
    * @param mixed $max Tout entier positif ou nul - Automatiquement plafonné à 9876543210
    * @param bool $leadingZeros Tenir compte des zéros du début
    * @return int
    */
   static function nbOfNumbersWithUniqueDigits($min, $max = self::GREATEST_NUMBER_WITH_UNIQUE_DIGITS,
                                               $leadingZeros = TRUE)
   {
      // valeurs numériques obligatoires
      if ( ! (ctype_digit("$min") || ctype_digit("$max"))) {
         return 0;
      }

      // plafonnement de la limite supérieure
      if (bccomp($max, self::GREATEST_NUMBER_WITH_UNIQUE_DIGITS) == 1) {
         $max = self::GREATEST_NUMBER_WITH_UNIQUE_DIGITS;
      }

      $comp = bccomp($min, $max);
      if ($comp === 1) {        // minimum > maximum
         return 0;
      }
      else
      if ($comp === 0) {         // minimum = maximum
         return (self::hasUniqueDigits($min)) ? 1 : 0;
      }

      $nb   = 0;
      $min = "$min";
      $max = "$max";

      // si zéros du début significatifs => égalise les longueurs des limites (complétion avec 0)
      $equalizeLength =
         function() use (&$min, &$max) {
            if (strlen($min) < strlen($max)) {
               $min = str_pad($min, strlen($max), '0', STR_PAD_LEFT);
            }
            else
            if (strlen($min) > strlen($max)) {
               $max = str_pad($max, strlen($min), '0', STR_PAD_LEFT);
            }
         };

      // si les zéros du début sont significatifs, on égalise les longueurs des limites
      if ($leadingZeros) {
         $equalizeLength();
      }

      // traitement des effets de bord (limite inférieure) : si dernier chiffre = 9
      // vérification manuelle de la validité puis on rajoute 1
      if ($min[strlen($min) - 1] == 9) {
         if (self::hasUniqueDigits($min)) {
            ++$nb;
         }
         $min = bcadd($min, 1);
      }

      // traitement des effets de bord (limite supérieure): si dernier chiffre = 0
      // vérification manuelle de la validité puis on retranche 1
      if ($max[strlen($max) - 1] == 0) {
         if (self::hasUniqueDigits($max)) {
            ++$nb;
         }
         $max = bcsub($max, 1);
      }

      // pour le traitement on égalise les longueurs des limites si cela n'a pas déjà été fait
      if (FALSE === $leadingZeros) {
         $equalizeLength();
      }

      // détermination des paliers pour le comptage des valeurs
      $steps = self::steps($min, $max);

      foreach($steps as $step) {
         $nb += self::countAllowedNumbers($step[0], $step[1], $leadingZeros);
      }
      return $nb;
   }

   /**
    * Indique si le nombre en paramètre n'est composé que de digits uniques
    * @param mixed $p Tout entier positif
    * @return bool
    */
   static function hasUniqueDigits($p) {
      return (ctype_digit("$p")) ? (count(array_flip(str_split($p, 1))) === strlen($p)) : FALSE;
   }

   /**
    * Décompose un nombre en paliers successifs de type x000->y999
    * @param mixed $mixRange Tout entier positif ou nul
    * @param mixed $maxRange Tout entier positif ou nul
    * @return array Array([] => array(0 => min, 1 => max))
    */
   static private function steps($minRange, $maxRange) {
      /*
      2 sens de parcours : croissant et décroissant
      Paliers si $pMin = 245600 et $pMax = 322799
      245600 -> 245609 :: sens croissant
      245610 -> 245699 ::       "
      245700 -> 245999 ::       "
      246000 -> 249999 ::       "
      250000 -> 299999 ::       "
      300000 -> 319999 :: sens décroissant (300000 = base minimum pour l'itération décroissante)
      320000 -> 321999 ::       "
      322000 -> 322699 ::       "
      322700 -> 322789 ::       "
      322790 -> 322799 ::       "
      */

      $descendingSearch = FALSE;

      $len   = strlen($minRange);
      $i     = $len;
      $min   = $minRange;
      $base  = $minRange;   // utilisé comme minimum pour la décomposition décroissante
      $steps = array();

      while (--$i >= 0) {
         $left  = substr($min, 0, $i);
         $right = str_repeat('9', $len - $i);
         $max   = $left . $right;
         $comp  = bccomp($maxRange, $max);

         if ($comp >= 0) {
            $steps[] = array($min, $max);
            $min     = bcadd($max, 1);
            $min     = str_pad($min, $len, '0', STR_PAD_LEFT);
            $base    = $min;

            if ($comp === 0) {
               break;
            }
         }
         else {
            $descendingSearch = TRUE;
            break;
         }
      }

      if ($descendingSearch) {
         $i   = $len;
         $max = $maxRange;

         while (--$i >= 0) {
            $left  = substr($max, 0, $i);
            $right = str_repeat('0', $len - $i);
            $min   = $left . $right;
            $comp  = bccomp($min, $base);

            if ($comp >= 0) {
               $steps[] = array($min, $max);

               if ($comp === 0) {
                  break;
               }

               $max = bcsub($min, 1);
            }
            else  {
               $steps[] = array($base, $max);
               break;
            }
         }
      }
      return $steps;
   }

   /**
    * Routine de comptage du nombre de nombres à digits uniques
    * qu'il est possible de créer entre deux limites
    * @param mixed $min Tout entier positif ou nul
    * @param mixed $max Tout entier positif ou nul
    * @param mixed $leadingZeros Zéros de début significatifs
    * @return int
    */
   static private function countAllowedNumbers($min, $max, $leadingZeros) {
      $nbAllowed = array();

      // suppression des zéros du début non significatifs
      if (FALSE === $leadingZeros) {
         $min = ($min == 0) ? '0' : ltrim($min, '0');
         $max = ($max == 0) ? '0' : ltrim($max, '0');
      }

      $iMax = strlen($min) - 1;

      // préparation du tableau d'analyse pour chaque position de digit
      for($i = 0 ; $i <= $iMax ; ++$i) {
         $structure[$i] = array('possible' => array(), 'forbidden' => array(), 'substract' => 0);
      }

      $i = -1;

      while(++$i <= $iMax) {
         $structure[$i]['possible'] = range($min[$i], $max[$i]);

         if ($min[$i] == $max[$i]) {
            // propagation de la valeur interdite à toutes les positions postérieures
            for($j = $i + 1 ; $j <= $iMax ; ++$j) {
               $structure[$j]['forbidden'][] = $min[$i];
            }
         }
         else {
            // propagation de la valeur choisie à toutes les positions postérieures
            for($j = $i + 1 ; $j <= $iMax ; ++$j) {
               ++$structure[$j]['substract'];
            }
         }
      }

      // comptage du nombre de valeurs possibles par position de digit
      foreach($structure as $value) {
         $nbAllowed[] = count(array_diff($value['possible'], $value['forbidden'])) - $value['substract'];
      }

      return (($nb = array_product($nbAllowed)) > 0) ? $nb : 0;
   }
}
?>