<?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;
}
}
?>
|
Download
