Short Unique Hexadecimal String in Python

Question

I need to generate a unique hexadecimal string in Python 3 that meets following requirements:

1. It should contain 6 characters
2. it should not contain just digits. There must be at least one character.
3. These generated strings should be random. They should not be in any order.
4. There should be minimum probability of conflict

I have considered uuid4(). But the problem is that it generates strings with too many characters and any substring of the generated string can contain all digits(i.e. no character) at some point.

Is there any other way to fulfill this conditions? Thanks in advance!

EDIT

Can we use a hash for example SHA-1 to fulfill above requirements?

Answer 1

Here's a simple method that samples evenly from all allowed strings. Sampling uniformly makes conflicts as rare as possible, short of keeping a log of previous keys or using a hash based on a counter (see below).

import random
digits = '0123456789'
letters = 'abcdef'
all_chars = digits + letters
length = 6

while True:

   val = ''.join(random.choice(all_chars) for i in range(length))

   # The following line might be faster if you only want hex digits.
   # It makes a long int with 24 random bits, converts it to hex,
   # drops '0x' from the start and 'L' from the end, then pads
   # with zeros up to six places if needed
   # val = hex(random.getrandbits(4*length))[2:-1].zfill(length)

   # test whether it contains at least one letter
   if not val.isdigit():
       break

# now val is a suitable string
print val
# 5d1d81

Alternatively, here's a somewhat more complex approach that also samples uniformly, but doesn't use any open-ended loops:

import random, bisect
digits = '0123456789'
letters = 'abcdef'
all_chars = digits + letters
length = 6

# find how many valid strings there are with their first letter in position i
pos_weights = [10**i * 6 * 16**(length-1-i) for i in range(length)]
pos_c_weights = [sum(pos_weights[0:i+1]) for i in range(length)]

# choose a random slot among all the allowed strings
r = random.randint(0, pos_c_weights[-1])

# find the position for the first letter in the string
first_letter = bisect.bisect_left(pos_c_weights, r)

# generate a random string matching this pattern
val = ''.join(
    [random.choice(digits) for i in range(first_letter)]
    + [random.choice(letters)]
    + [random.choice(all_chars) for i in range(first_letter + 1, length)]
)

# now val is a suitable string
print val
# 4a99f0

And finally, here's an even more complex method that uses the random number r to index directly into the entire range of allowed values, i.e., this converts any number in the range of 0-15,777,216 into a suitable hex string. This could be used to completely avoid conflicts (discussed more below).

import random, bisect
digits = '0123456789'
letters = 'abcdef'
all_chars = digits + letters
length = 6

# find how many valid strings there are with their first letter in position i
pos_weights = [10**i * 6 * 16**(length-1-i) for i in range(length)]
pos_c_weights = [sum(pos_weights[0:i+1]) for i in range(length + 1)]

# choose a random slot among all the allowed strings
r = random.randint(0, pos_c_weights[-1])

# find the position for the first letter in the string
first_letter = bisect.bisect_left(pos_c_weights, r) - 1

# choose the corresponding string from among all that fit this pattern
offset = r - pos_c_weights[first_letter]
val = ''
# convert the offset to a collection of indexes within the allowed strings 
# the space of allowed strings has dimensions
# 10 x 10 x ... (for digits) x 6 (for first letter) x 16 x 16 x ... (for later chars)
# so we can index across it by dividing into appropriate-sized slices
for i in range(length):
    if i < first_letter:
        offset, v = divmod(offset, 10)
        val += digits[v]
    elif i == first_letter:
        offset, v = divmod(offset, 6)
        val += letters[v]
    else:
        offset, v = divmod(offset, 16)
        val += all_chars[v]

# now val is a suitable string
print val
# eb3493

Uniform Sampling

I mentioned above that this samples uniformly across all allowed strings. Some other answers here choose 5 characters completely at random and then force a letter into the string at a random position. That approach produces more strings with multiple letters than you would get randomly. e.g., that method always produces a 6-letter string if letters are chosen for the first 5 slots; however, in this case the sixth selection should actually only have a 6/16 chance of being a letter. Those approaches can't be fixed by forcing a letter into the sixth slot only if the first 5 slots are digits. In that case, all 5-digit strings would automatically be converted to 5 digits plus 1 letter, giving too many 5-digit strings. With uniform sampling, there should be a 10/16 chance of completely rejecting the string if the first 5 characters are digits.

Here are some examples that illustrate these sampling issues. Suppose you have a simpler problem: you want a string of two binary digits, with a rule that at least one of them must be a 1. Conflicts will be rarest if you produce 01, 10 or 11 with equal probability. You can do that by choosing random bits for each slot, and then throwing out the 00's (similar to my approach above).

But suppose you instead follow this rule: Make two random binary choices. The first choice will be used as-is in the string. The second choice will determine the location where an additional 1 will be inserted. This is similar to the approach used by the other answers here. Then you will have the following possible outcomes, where the first two columns represent the two binary choices:

0 0 -> 10
0 1 -> 01
1 0 -> 11
1 1 -> 11

This approach has a 0.5 chance of producing 11, or 0.25 for 01 or 10, so it will increase the risk of collisions among 11 results.

You could try to improve this as follows: Make three random binary choices. The first choice will be used as-is in the string. The second choice will be converted to a 1 if the first choice was a 0; otherwise it will be added to the string as-is. The third choice will determine the location where the second choice will be inserted. Then you have the following possible outcomes:

0 0 0 -> 10 (second choice converted to 1)
0 0 1 -> 01 (second choice converted to 1)
0 1 0 -> 10
0 1 1 -> 01
1 0 0 -> 10
1 0 1 -> 01
1 1 0 -> 11
1 1 1 -> 11

This gives 0.375 chance for 01 or 10, and 0.25 chance for 11. So this will slightly increase the risk of conflicts between duplicate 10 or 01 values.

Reducing Conflicts

If you are open to using all letters instead of just 'a' through 'f' (hexadecimal digits), you could alter the definition of letters as noted in the comments. This will give much more diverse strings and much less chance of conflict. If you generated 1,000 strings allowing all upper- and lowercase letters, you'd only have about a 0.0009% chance of generating any duplicates, vs. 3% chance with hex strings only. (This will also virtually eliminate double-passes through the loop.)

If you really want to avoid conflicts between strings, you could store all the values you've generated previously in a set and check against that before breaking from the loop. This would be good if you are going to generate fewer than about 5 million keys. Beyond that, you'd need quite a bit of RAM to hold the old keys, and it might take a few runs through the loop to find an unused key.

If you need to generate more keys than that, you could encrypt a counter, as described at Generating non-repeating random numbers in Python. The counter and its encrypted version would both be ints in the range of 0 to 15,777,216. The counter would just count up from 0, and the encrypted version would look like a random number. Then you would convert the encrypted version to hex using the third code example above. If you do this, you should generate a random encryption key at the start, and change the encryption key each time the counter rolls past your maximum, to avoid producing the same sequence again.

Answer 2

Note: Updated the answer for hexadecimal unique string. Earlier I assumed for alhanumeric string.

You may create your own unique function using uuid and random library

>>> import uuid
>>> import random
# Step 1: Slice uuid with 5 i.e. new_id = str(uuid.uuid4())[:5] 
# Step 2: Convert string to list of char i.e. new_id = list(new_id)
>>> uniqueval = list(str(uuid.uuid4())[:5])
# uniqueval = ['f', '4', '4', '4', '5']

# Step 3: Generate random number between 0-4 to insert new char i.e.
#         random.randint(0, 4)
# Step 4: Get random char between a-f (for Hexadecimal char) i.e.
#         chr(random.randint(ord('a'), ord('f')))
# Step 5: Insert random char to random index
>>> uniqueval.insert(random.randint(0, 4), chr(random.randint(ord('a'), ord('f'))))
# uniqueval = ['f', '4', '4', '4', 'f', '5']

# Step 6: Join the list
>>> uniqueval = ''.join(uniqueval)
# uniqueval = 'f444f5'

Answer 3

The following approach works as follows, first pick one random letter to ensure rule 2, then select 4 random entries from the list of all available characters. Shuffle the resulting list. Lastly prepend one value taken from the list of all entries except 0 to ensure the string has 6 characters.

import random

all = "0123456789abcdef"
result = [random.choice('abcdef')] + [random.choice(all) for _ in range(4)]
random.shuffle(result)
result.insert(0, random.choice(all[1:]))
print(''.join(result))

Giving you something like:

3b7a4e

This approach avoids having to repeatedly check the result to ensure that it satisfies the rules.

Answer 4

This function returns the nth string conforming to your requirements, so you can simply generate unique integers and convert them using this function.

def inttohex(number, digits):
    # there must be at least one character:
    fullhex = 16**(digits - 1)*6
    assert number < fullhex
    partialnumber, remainder = divmod(number, digits*6)
    charposition, charindex = divmod(remainder, digits)
    char = ['a', 'b', 'c', 'd', 'e', 'f'][charposition]
    hexconversion = list("{0:0{1}x}".format(partialnumber, digits-1))
    hexconversion.insert(charposition, char)

    return ''.join(hexconversion)

Now you can get a particular one using for instance

import random

digits = 6
inttohex(random.randint(0, 6*16**(digits-1)), digits)

You can't have maximum randomness along with minimum probability of conflict. I recommend keeping track of which numbers you have handed out or if you are looping through all of them somehow, using a randomly sorted list.