Generating unique 6 digit code

问题:

I'm generating a 6 digit code from the following characters. These will be used to stamp on stickers.
They will be generated in batches of 10k or less (before printing) and I don't envisage there will ever be more than 1-2 million total (probably much less).
After I generate the batches of codes, I'll check the MySQL database of existing codes to ensure there are no duplicates.

// exclude problem chars: B8G6I1l0OQDS5Z2

$characters = 'ACEFHJKMNPRTUVWXY4937';

$string = '';

for ($i = 0; $i < 6; $i++) {
    $string .= $characters[rand(0, strlen($characters) - 1)];
}   

return $string;

1. Is this a solid approach to generating the code?
2. How many possible permutations would there be? (6 Digit code from pool of 21 characters). Sorry math isn't my strong point

回答1:

21^6 = 85766121 possibilities.

Using a DB and storing used values is bad. If you want to fake randomness you can use the following:

Reduce to 19 possible numbers and make use of the fact that groups of order p^k where p is an odd prime are always cyclic.

Take the group of order 7^19, using a generator co-prime to 7^19 (I'll pick 13^11, you can choose anything not divisible by 7).

Then the following works:

$previous = 0;

function generator($previous)
{

  $generator = pow(13,11);
  $modulus = pow(7,19); //int might be too small
  $possibleChars = "ACEFHJKMNPRTUVWXY49";

  $previous = ($previous + $generator) % $modulus;
  $output='';
  $temp = $previous;

  for($i = 0; $i < 6; $i++) {
    $output += $possibleChars[$temp % 19];
    $temp = $temp / 19;
  }

  return $output;
}

It will cycle through all possible values and look a little random unless they go digging. An even safer alternative would be multiplicative groups but I forget my math already :(

回答2:

• There is a lot of possible combination with or without repetition so your logic would be sufficient
• Collision would be frequent because you are using rand see str_shuffle and randomness.
• Change rand to mt_rand
• Use fast storage like memcached or redis not MySQL when checking

Total Possibility

21 ^ 6 = 85,766,121

85,766,121 should be ok , To add database to this generation try:

Example

$prifix = "stamp.";

$cache = new Memcache();
$cache->addserver("127.0.0.1");

$stamp = myRand(6);
while($cache->get($prifix . $stamp)) {
    $stamp = myRand(6);
}
echo $stamp;

Function Used

function myRand($no, $str = "", $chr = 'ACEFHJKMNPRTUVWXY4937') {
    $length = strlen($chr);
    while($no --) {
        $str .= $chr{mt_rand(0, $length- 1)};
    }
    return $str;
}

回答3:

as Baba said generating a string on the fly will result in tons of collisions. the closer you will go to 80 millions already generated ones the harder it will became to get an available string

another solution could be to generate all possible combinations once, and store each of them in the database already, with some boolean column field that marks if a row/token is already used or not

then to get one of them

SELECT * FROM tokens WHERE tokenIsUsed = 0 ORDER BY RAND() LIMIT 0,1

and then mark it as already used

UPDATE tokens SET tokenIsUsed = 1 WHERE token = ...

回答4:

You would have 21 ^ 6 codes = 85 766 121 ~ 85.8 million codes!

To generate them all (which would take some time), look at the selected answer to this question: algorithm that will take numbers or words and find all possible combinations.

回答5:

I had the same problem, and I found very impressive open source solution:

http://www.hashids.org/php/

You can take and use it, also it's worth it to look in it's source code to understand what's happening under the hood.

回答6:

Or... you can encode username+datetime in md5 and save to database, this for sure will generate an unique code ;)