How can I generate a unique, predictable, repeatable, non sequential alphanumeric identifier?

Question

I have to generate identifiers composed of four alphanumerical characters, e.g. B41F.

I have the following requirements:

1. Each identifier must be unique (there is no central location to lookup existing identifiers)
2. The identifier must not be obviously sequential (e.g. 1A01, 1A02)
3. It must be predictable
4. It must be repeatable using solely the identifier index (on two different environment, the Nth identifier generated, which has index N, must be the same)

The problem is generic to any language. My implementation will be done in dart.

I think this could be done with a PRNG and some LUT, but I could not find any implementation or pseudo-code that respects requirement 4) without replaying the whole sequence. Also, some PRNG implementation have a random component that is not guaranteed to be repeatable over library update.

How can I achieve this? I'm looking for pseudo-code, code or hints.

Answer 1

You should not use a PRNG when identifiers must be unique. RNGs do not promise uniqueness. Some might have a long period before they repeat, but that's at their full bit-range, reducing it to a smaller number may cause conflicts earlier.

Your identifiers are really just numbers in base 36, so you need something like shuffle(index).toRadixString(36) to generate it.

The tricky bit is the shuffle function which must be a permutations of the numbers 0..36^4-1, one which looks random (non-sequential), but can be computed (efficiently?) for any input.

Since 36^4 is not a power of 2, most of the easy bit-shuffles likely won't work.

If you can live with 32^4 numbers only (2^20 ~ 1M) it might be easier. Then you can also choose to drop O, I, 0 and 1 from the result, which might make it easier to read.

In that case, I'd do something primitive (not cryptographically secure at all), like:

// Represent 20-bit numbers
String represent(int index) {
  RangeError.checkValueInInterval(index, 0, 0xFFFFF, "index");
  var digits = "23456789ABCDEFGHJKLMNPQRSTUVWXYZ";
  return "${digits[(index >> 15) & 31]}${digits[(index >> 10) & 31]}"
       "${digits[(index >> 5) & 31]}${digits[index & 31]}";
}

// Completely naive number shuffler for 20-bit numbers.
// All numbers made up on the spot.
int shuffle(int index) {
  RangeError.checkValueInInterval(index, 0, 0xFFFFF, "index");
  index ^= 0x35712;
  index ^= index << 15;
  index ^= index << 4;
  index ^= index << 12;
  index ^= index << 7;
  index ^= index << 17;
  return index & 0xFFFFF; // 20 bit only.
}

If you really want the full 36^4 range to be used, I'd probably do something like the shuffle, but in base-six arithmetic. Maybe:

String represent(int index) =>   
    RangeError.checkValueInInterval(index, 0, 1679615, "index")
        .toRadixString(36).toUpperCase();

int shuffle(int index) {
  RangeError.checkValueInInterval(index, 0, 1679615, "index");
  const seed = [1, 4, 2, 5, 0, 3, 1, 4]; // seed.
  var digits = List<int>.filled(8, 0);
  for (var i = 0; i < 8; i++) {
    digits[i] = index.remainder(6);
    index = index ~/ 6;
  }

  void shiftAdd(List<int> source, int shift, int times) {
    for (var n = digits.length - 1 - shift; n >= 0; n--) {
      digits[shift + n] = (digits[shift + n] + source[n] * times).remainder(6);
    }
  }

  shiftAdd(seed, 0, 1);
  shiftAdd(digits, 3, 2);
  shiftAdd(digits, 5, 1);
  shiftAdd(digits, 2, 5);
  var result = 0;
  for (var i = digits.length - 1; i >= 0; i--) {
    result = result * 6 + digits[i];
  }
  return result;
}

Again, this is something I made up on the spot, it "shuffles", but does not promise anything about the properties of the result, other than that they don't look sequential.