Generating unique 6 digit code

Question

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

Solution 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 :(

Solution 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;
}

Solution 3

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.

Comments

[Jean-Bernard Pellerin]

you mixed up your base and exponent, and mangled your digit separation, it's ~86 million

[Quad6]

The generated codes need to be stored as they are associated with stamps (products) which will have info associated with them. If I generate 10k of codes then a month later another 10k, I need to somehow check that there are no duplicates in this new 10k batch.

[Quad6]

Thanks. 86 mill is sufficient. I will use your suggestion of mt_rand. I'm not sure how memcached can be used to check that codes in a newly generated batch don't already existing in MySQL (containing all previously generated batches of codes). For printing purposes, I imagine generating 10k or so codes at a time

[Jean-Bernard Pellerin]

I've posted how to ignore duplicates, but if you're storing additional info anyways disregard this answer.

[CSᵠ]

@Jean-BernardPellerin php-ized you code, hope you don't mind, please check to see if everything is allright

[keen]

will this be unique every time or do i need to check that manually ? and i don't want it to be from 21 chars only , anything will ok for me.

[PHP_USER1]

how to use this answere

[FreeBird]

6^19 or 19^6? 6 is not an odd prime, so I'm assuming you meant the latter. In which case your choice of generator is not co-prime to it (19^11) - 11^19 looks OK. I was looking for 5-character codes and arrived at this answer; I am using 23^5 (removed I, O and Q from the alphabet) as modulus and 19^11 for the generator which seems to work for me.

[yudijohn]

it should be $output .= $possibleChars[$temp % 19];