Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 5 sur 5
  1. #1
    Modérateur
    Avatar de rawsrc
    Homme Profil pro Martin
    Dev indep
    Inscrit en
    mars 2004
    Messages
    3 579
    Détails du profil
    Informations personnelles :
    Nom : Homme Martin
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Dev indep

    Informations forums :
    Inscription : mars 2004
    Messages : 3 579
    Points : 8 287
    Points
    8 287

    Par défaut Calcul du nombre de nombres à digits distincts entre deux bornes

    Bonjour,

    Dans le cadre de mon taf, j'ai eu à pondre un algo de calcul du nombre de nombres entiers composés de digits distincts qu'il est possible de créer entre deux limites.
    Je n'utilise pas l'approche mathématique mais une approche intervallaire optimisée (contrainte).
    Vu qu'on est susceptible de manipuler des grands nombres, la classe utilise BCMATH pour certaines opérations.
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    327
    328
    329
    <?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   : PHP 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.0
     * @author Martin Lacroix
     */
    class Calculus {
     
       /**
        * 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 aynant 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 $pMin Tout entier positif ou nul
        * @param mixed $pMax Tout entier positif ou nul
        * @param bool $pLeadingZeros Tenir compte des zéros du début
        * @return int
        * @static
        */
       static function nbOfNumbersWithUniqueDigits($pMin, $pMax, $pLeadingZeros = TRUE) {
     
          # valeurs numériques obligatoires
          if ( ! (ctype_digit("$pMin") || ctype_digit("$pMax"))) {
             return 0;
          }
     
          $comp = bccomp($pMin, $pMax);
          if ($comp == 1) {          # minimum < maximum
             return 0;
     
          } elseif ($comp == 0) {    # minimum = maximum
             return (self::hasUniqueDigits($pMin)) ? 1 : 0;
          }
     
          $nb   = 0;
          $pMin = (string) $pMin;
          $pMax = (string) $pMax;
     
          # si zéros du début significatifs => égalise les longueurs des limites (complétion avec 0)
          $equalizeLength = function() use (&$pMin, &$pMax) {
                               if (strlen($pMin) < strlen($pMax)) {
                                  $pMin = str_pad($pMin, strlen($pMax), '0', STR_PAD_LEFT);
     
                               } elseif (strlen($pMin) > strlen($pMax)) {
                                  $pMax = str_pad($pMax, strlen($pMin), '0', STR_PAD_LEFT);
                               }
                            };
     
          # si les zéros du début sont significatifs, on égalise les longueurs des limites
          if ($pLeadingZeros) {
             $equalizeLength();
          }
     
          # traitement des effets de bord (limite inférieure) : si dernier chiffre = 9
          # vérification manuelle de la validité puis on rajoute 1
          if ($pMin[strlen($pMin) - 1] == 9) {
             if (self::hasUniqueDigits($pMin)) {
                ++$nb;
             }
             $pMin = bcadd($pMin, 1);
          }
     
          # traitement des effets de bord (limite supérieure): si dernier chiffre = 0
          # vérification manuelle de la validité puis on retranche 1
          if ($pMax[strlen($pMax) - 1] == 0) {
             if (self::hasUniqueDigits($pMax)) {
                ++$nb;
             }
             $pMax = bcsub($pMax, 1);
          }
     
          # pour le traitement on égalise les longueurs des limites si cela n'a pas déjà été fait
          if ($pLeadingZeros == FALSE) {
             $equalizeLength();
          }
     
          # détermination des paliers pour le comptage des valeurs
          $steps = self::steps($pMin, $pMax);
     
          foreach($steps as $step) {
             $nb += self::countAllowedNumbers($step[0], $step[1], $pLeadingZeros);
          }
          return $nb;
       }
     
       /**
        * Renvoie le nombre de digits identiques successifs à partir d'une position donnée 
        * et d'un sens de parcours
        * La valeur du digit est déterminé 
        *    - soit automatiquement en fonction de la position de début 
        *    - soit manuellement (digit ou suite de digits recherché)
        * Le sens du parcours est fonction de la position de fin
        * @param mixed $p
        * @param mixed $pPosStart numeric|FIRST|LAST Le 1er digit est en position 0
        * @param mixed $pPosEnd numeric|FIRST|LAST Le 1er digit est en position 0
        * @param mixed $pDigit numeric|AUTO Si AUTO La valeur du digit est fonction de $pPosStart
        * @return int
        * @static
        */
       static function nbOfSameDigits($p, $pPosStart = 'FIRST', $pPosEnd = 'LAST', $pDigit = 'AUTO') {
     
          # vérification d'une limite : renvoie la position numérique correspondante
          $checkPos = function($pPos) use ($p) {
                         $max = strlen($p) - 1;
                         if ($pPos == 'FIRST') {
                            return 0;
     
                         } elseif ($pPos == 'LAST') {
                            return $max;
     
                         } elseif (ctype_digit("$pPos")) {
                            return ($pPos > $max) ? $max : $pPos;
                         }
                         return 0;
                      };
     
          $p  = (string) $p;
          $nb = 0;
          $i  = $checkPos($pPosStart);  # position DEBUT
          $j  = $checkPos($pPosEnd);    # position FIN
     
          if ($pDigit == 'AUTO') {
             $digit = (int) $p[$i];
             $nb = 1;
     
          } else {
             if ($pDigit != $p[$i]) {
                return 0;
     
             } else {
                $digit = (int) $pDigit;
                $nb = 1;
             }
          }
     
          if ( ! is_int($digit)) {
             return 0;
          }
     
          # comptage du nombre d'occurrences successives du même digit en fonction du sens de parcours
          if ($i < $j) {          # sens : DEBUT -> FIN
             while((++$i <= $j) && (((int) $p[$i]) === $digit)) {
                ++$nb;
             }
     
          } elseif ($i > $j) {    # sens : FIN -> DEBUT
             while((--$i >= $j) && (((int) $p[$i]) === $digit)) {
                ++$nb;
             }
          }
          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
        */
       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 $pMin Tout entier positif ou nul
        * @param mixed $pMax Tout entier positif ou nul
        * @return array Array([] => array(0 => min, 1 => max))
        * @static
        */
       static private function steps($pMin, $pMax) {
          /**
           * 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($pMin);
          $i     = $len;
          $min   = $pMin;
          $base  = $pMin;   # 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($pMax, $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 = $pMax;
     
             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 $pMin Tout entier positif ou nul
        * @param mixed $pMax Tout entier positif ou nul
        * @param mixed $pLeadingZeros Zéros de début significatifs
        * @return int
        * @static
        */
       static private function countAllowedNumbers($pMin, $pMax, $pLeadingZeros) {
          $nbAllowed = array();
     
          # suppression des zéros du début non significatifs
          if ($pLeadingZeros == FALSE) {
             $pMin = ($pMin == 0) ? '0' : ltrim($pMin, '0');
             $pMax = ($pMax == 0) ? '0' : ltrim($pMax, '0');
          }
     
          $iMax = strlen($pMin) - 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($pMin[$i], $pMax[$i]);
     
             if ($pMin[$i] == $pMax[$i]) {
                # propagation de la valeur interdite à toutes les positions postérieures
                for($j = $i + 1 ; $j <= $iMax ; ++$j) {
                   $structure[$j]['forbidden'][] = $pMin[$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;
       }
    }
    ?>
    Pour tester la classe voici quelques exemples :
    Code :
    1
    2
    3
    4
    5
    6
    $a = Calculus::nbOfNumbersWithUniqueDigits(465, 999);       # Attendu   388
    $b = Calculus::nbOfNumbersWithUniqueDigits(100, 770);       # Attendu   488
    $c = Calculus::nbOfNumbersWithUniqueDigits(699, 705);       # Attendu     5
    $d = Calculus::nbOfNumbersWithUniqueDigits(245600, 322800); # Attendu 13140
    $e = Calculus::nbOfNumbersWithUniqueDigits(0, 100, FALSE);  # Attendu    91
    $f = Calculus::nbOfNumbersWithUniqueDigits(0, 100, TRUE);   # Attendu    72
    # Dans la Création, tout est permis mais tout n'est pas utile...

  2. #2
    Modérateur

    Inscrit en
    septembre 2010
    Messages
    7 957
    Détails du profil
    Informations forums :
    Inscription : septembre 2010
    Messages : 7 957
    Points : 9 498
    Points
    9 498

    Par défaut

    sympa, j'ai essayé de faire un truc aussi, version réflexion basique (ça se ressent c'est pas optimisé du-tout )

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    function unique_digit($min, $max)
    {
        $count = 0;
     
        for($i = $min; $i < $max; ++$i)
        {
            $split = str_split($i);
     
            if(count(array_unique($split)) === count($split))
            {
                ++$count;
            }
     
            unset($split);
        }
     
        return $count;
    }

  3. #3
    Modérateur
    Avatar de rawsrc
    Homme Profil pro Martin
    Dev indep
    Inscrit en
    mars 2004
    Messages
    3 579
    Détails du profil
    Informations personnelles :
    Nom : Homme Martin
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Dev indep

    Informations forums :
    Inscription : mars 2004
    Messages : 3 579
    Points : 8 287
    Points
    8 287

    Par défaut

    Ah ça je suis bien d'accord avec toi, la méthode itérative est à oublier, elle a trop d'appétit.
    # Dans la Création, tout est permis mais tout n'est pas utile...

  4. #4
    Modérateur
    Avatar de rawsrc
    Homme Profil pro Martin
    Dev indep
    Inscrit en
    mars 2004
    Messages
    3 579
    Détails du profil
    Informations personnelles :
    Nom : Homme Martin
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Dev indep

    Informations forums :
    Inscription : mars 2004
    Messages : 3 579
    Points : 8 287
    Points
    8 287

    Par défaut

    @stealth35 : Tu aurais pu améliorer un peu les perf de ton script avec ça :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    function unique_digit($min, $max) {
        $nb = 0;
        $i = $min - 1;
     
        while (++$i <= $max) {
           $nb += (count(array_flip(str_split($i, 1))) == strlen($i));
        }
     
        return $nb;
    }
    Après c'est comme tout, c'est pas génial.
    J'ai testé les 3 scripts pour les limites 245600 - 322800
    Cela donne :
    script stealth35 : 0.37s
    script stealth35 optimisé : 0.29s
    mon script : 0.0008s
    # Dans la Création, tout est permis mais tout n'est pas utile...

  5. #5
    Modérateur
    Avatar de rawsrc
    Homme Profil pro Martin
    Dev indep
    Inscrit en
    mars 2004
    Messages
    3 579
    Détails du profil
    Informations personnelles :
    Nom : Homme Martin
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Dev indep

    Informations forums :
    Inscription : mars 2004
    Messages : 3 579
    Points : 8 287
    Points
    8 287

    Par défaut

    Bonjour,

    J'ai vu une faiblesse de mon script version 1.0.0.
    Dans le cas où l'on passait un $pMax très très grand (ex : 128 digits) les perfs s'effondraient alors qu'il était possible d'optimiser cet aspect.

    Voici la version 1.0.1 du script avec le plafonnement de la limite $pMax par le plus grand nombre à digits uniques possible : 9876543210.
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    327
    328
    329
    330
    331
    332
    333
    334
    335
    336
    337
    <?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 $pMin Tout entier positif ou nul
        * @param mixed $pMax Tout entier positif ou nul - Automatiquement plafonné à 9876543210
        * @param bool $pLeadingZeros Tenir compte des zéros du début
        * @return int
        * @static
        */
       static function nbOfNumbersWithUniqueDigits($pMin, $pMax = self::GREATEST_NUMBER_WITH_UNIQUE_DIGITS, 
                                                   $pLeadingZeros = TRUE) 
       {
          # valeurs numériques obligatoires
          if ( ! (ctype_digit("$pMin") || ctype_digit("$pMax"))) {
             return 0;
          }
     
          # plafonnement de la limite supérieure
          if (bccomp($pMax, self::GREATEST_NUMBER_WITH_UNIQUE_DIGITS) == 1) {
             $pMax = self::GREATEST_NUMBER_WITH_UNIQUE_DIGITS;
          }
     
          $comp = bccomp($pMin, $pMax);
          if ($comp == 1) {          # minimum > maximum
             return 0;
     
          } elseif ($comp == 0) {    # minimum = maximum
             return (self::hasUniqueDigits($pMin)) ? 1 : 0;
          }
     
          $nb   = 0;
          $pMin = (string) $pMin;
          $pMax = (string) $pMax;
     
          # si zéros du début significatifs => égalise les longueurs des limites (complétion avec 0)
          $equalizeLength = function() use (&$pMin, &$pMax) {
                               if (strlen($pMin) < strlen($pMax)) {
                                  $pMin = str_pad($pMin, strlen($pMax), '0', STR_PAD_LEFT);
     
                               } elseif (strlen($pMin) > strlen($pMax)) {
                                  $pMax = str_pad($pMax, strlen($pMin), '0', STR_PAD_LEFT);
                               }
                            };
     
          # si les zéros du début sont significatifs, on égalise les longueurs des limites
          if ($pLeadingZeros) {
             $equalizeLength();
          }
     
          # traitement des effets de bord (limite inférieure) : si dernier chiffre = 9
          # vérification manuelle de la validité puis on rajoute 1
          if ($pMin[strlen($pMin) - 1] == 9) {
             if (self::hasUniqueDigits($pMin)) {
                ++$nb;
             }
             $pMin = bcadd($pMin, 1);
          }
     
          # traitement des effets de bord (limite supérieure): si dernier chiffre = 0
          # vérification manuelle de la validité puis on retranche 1
          if ($pMax[strlen($pMax) - 1] == 0) {
             if (self::hasUniqueDigits($pMax)) {
                ++$nb;
             }
             $pMax = bcsub($pMax, 1);
          }
     
          # pour le traitement on égalise les longueurs des limites si cela n'a pas déjà été fait
          if ($pLeadingZeros == FALSE) {
             $equalizeLength();
          }
     
          # détermination des paliers pour le comptage des valeurs
          $steps = self::steps($pMin, $pMax);
     
          foreach($steps as $step) {
             $nb += self::countAllowedNumbers($step[0], $step[1], $pLeadingZeros);
          }
          return $nb;
       }
     
       /**
        * Renvoie le nombre de digits identiques successifs à partir d'une position donnée 
        * et d'un sens de parcours
        * La valeur du digit est déterminé 
        *    - soit automatiquement en fonction de la position de début 
        *    - soit manuellement (digit ou suite de digits recherché)
        * Le sens du parcours est fonction de la position de fin
        * @param mixed $p
        * @param mixed $pPosStart numeric|FIRST|LAST Le 1er digit est en position 0
        * @param mixed $pPosEnd numeric|FIRST|LAST Le 1er digit est en position 0
        * @param mixed $pDigit numeric|AUTO Si AUTO La valeur du digit est fonction de $pPosStart
        * @return int
        * @static
        */
       static function nbOfSameDigits($p, $pPosStart = 'FIRST', $pPosEnd = 'LAST', $pDigit = 'AUTO') {
     
          # vérification d'une limite : renvoie la position numérique correspondante
          $checkPos = function($pPos) use ($p) {
                         $max = strlen($p) - 1;
                         if ($pPos == 'FIRST') {
                            return 0;
     
                         } elseif ($pPos == 'LAST') {
                            return $max;
     
                         } elseif (ctype_digit("$pPos")) {
                            return ($pPos > $max) ? $max : $pPos;
                         }
                         return 0;
                      };
     
          $p  = (string) $p;
          $nb = 0;
          $i  = $checkPos($pPosStart);  # position DEBUT
          $j  = $checkPos($pPosEnd);    # position FIN
     
          if ($pDigit == 'AUTO') {
             $digit = (int) $p[$i];
             $nb = 1;
     
          } else {
             if ($pDigit != $p[$i]) {
                return 0;
     
             } else {
                $digit = (int) $pDigit;
                $nb = 1;
             }
          }
     
          if ( ! is_int($digit)) {
             return 0;
          }
     
          # comptage du nombre d'occurrences successives du même digit en fonction du sens de parcours
          if ($i < $j) {          # sens : DEBUT -> FIN
             while((++$i <= $j) && (((int) $p[$i]) === $digit)) {
                ++$nb;
             }
     
          } elseif ($i > $j) {    # sens : FIN -> DEBUT
             while((--$i >= $j) && (((int) $p[$i]) === $digit)) {
                ++$nb;
             }
          }
          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
        */
       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 $pMin Tout entier positif ou nul
        * @param mixed $pMax Tout entier positif ou nul
        * @return array Array([] => array(0 => min, 1 => max))
        * @static
        */
       static private function steps($pMin, $pMax) {
          /**
           * 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($pMin);
          $i     = $len;
          $min   = $pMin;
          $base  = $pMin;   # 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($pMax, $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 = $pMax;
     
             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 $pMin Tout entier positif ou nul
        * @param mixed $pMax Tout entier positif ou nul
        * @param mixed $pLeadingZeros Zéros de début significatifs
        * @return int
        * @static
        */
       static private function countAllowedNumbers($pMin, $pMax, $pLeadingZeros) {
          $nbAllowed = array();
     
          # suppression des zéros du début non significatifs
          if ($pLeadingZeros == FALSE) {
             $pMin = ($pMin == 0) ? '0' : ltrim($pMin, '0');
             $pMax = ($pMax == 0) ? '0' : ltrim($pMax, '0');
          }
     
          $iMax = strlen($pMin) - 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($pMin[$i], $pMax[$i]);
     
             if ($pMin[$i] == $pMax[$i]) {
                # propagation de la valeur interdite à toutes les positions postérieures
                for($j = $i + 1 ; $j <= $iMax ; ++$j) {
                   $structure[$j]['forbidden'][] = $pMin[$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;
       }
    }
    ?>
    # Dans la Création, tout est permis mais tout n'est pas utile...

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •