3
$\begingroup$

I want to generate a random list of six characters that only contain characters from "0...9" and "A...Z".

For this I can define

ToCharacterCode[{"ABCDEFGHIJKLMONPQRSTUVWXYZ", "0123456789"}]

I can modify the answer here as

rndnew = FromCharacterCode@
 RandomChoice[Join @@ Range[{48, 65}, {57, 90}], #] &

I can now generate five of these strings by doing

rndnew[{5, 6}]

This results in something like

{"35UVUS", "F7WIJG", "PQSBHF", "PIHTSW", "R3MDM6"}

My question is how can I guarantee that these strings have no collisions (I know this is a very large space)? Is there a better way to code this using random over the range of the size of this set (like a linear congruential generator with that range) to make sure the strings are unique or is there a facility in Mathematica to do that?

$\endgroup$
  • 5
    $\begingroup$ replace RandomChoice with RandomSample? $\endgroup$ – kglr Dec 13 '18 at 14:20
  • $\begingroup$ @kglr: I will certainly look into that. Thanks for the pointer! $\endgroup$ – Moo Dec 13 '18 at 14:21
  • 2
    $\begingroup$ When a function is close to what you want, look at the See Also section of that function's documentation. $\endgroup$ – Bob Hanlon Dec 13 '18 at 14:39
  • $\begingroup$ Sorry that I'm not a Mathematica user, so just provide my thought on solving this in pseudo code: while less than 5 strings in the collection: generate a random string if new string already exists in the collection: do nothing else: add it to the collection No collisions guaranteed, but might take a while. $\endgroup$ – Kyle R. Dec 14 '18 at 0:41
6
$\begingroup$

Just changing RandomChoice to RandomSample doesn't help, since RandomSample just means that none of the characters are repeated, and clearly you want to allow repeated characters, since one of your strings is "35UVUS". One idea is to oversample and remove duplicates. For example:

SeedRandom[1]
Take[
    DeleteDuplicates[rndnew[{10, 6}]],
    UpTo[5]
]

{"K1263G", "SXVXHC", "UO2PBL", "EC1FTJ", "0TKLEH"}

Another possibility is to index the possible random strings, and then do a random sample from the possible indices. For your case, the number of possible strings is simply 36^6. To convert from an index to a string:

characters = Join[CharacterRange["A","Z"], CharacterRange["0","9"]];

fromIndex[index_, len_] := StringJoin[
    characters[[1+IntegerDigits[index, 36, len]]]
]

Then, a function that returns n samples of length len strings:

sample[n_, len_] := fromIndex[#, len]& /@ RandomSample[1 ;; 36^len, n]

Example:

SeedRandom[1]
sample[5, 6]

{"0621O7", "0WH6XW", "ODLV4Z", "KWSN6U", "AMOSFA"}

$\endgroup$
  • $\begingroup$ Is there a way to generate some number of these, keep the state of the RNG and use it to reseed from that point moving forward so we can maintain uniqueness of all six-characters over time? $\endgroup$ – Moo Dec 13 '18 at 16:18
  • $\begingroup$ @Moo Not that I'm aware of. Do you know how many unique strings you want in total? $\endgroup$ – Carl Woll Dec 13 '18 at 16:49
  • $\begingroup$ If I am doing my math correctly, we have 6-character strings where strings can repeat, then there are $26$ letters plus $10$ digits in the pool of characters, giving us $36$ in all per character. This means we would have $36^6 = 2176782336$ combinations. $\endgroup$ – Moo Dec 13 '18 at 16:52
  • 1
    $\begingroup$ @Moo There are 36^6 total strings, but how many do you want to generate? There is no point in using a random approach if you want to generate all of them. $\endgroup$ – Carl Woll Dec 13 '18 at 17:04
  • $\begingroup$ CarlWoll: The issue is that I would generate something like $10000$ at a time, use them and then generate a new batch and over time, duplicates matter. Maybe there is a better way based on that, but I haven't thought about it. I am not sure I would ever use up the total number shown, but it can certainly be over several million of them over time. $\endgroup$ – Moo Dec 13 '18 at 17:22
3
$\begingroup$
RandomSample[
 Union[CharacterRange["a", "z"], CharacterRange["0", "9"]], 6]

or

RandomSample[Flatten[CharacterRange @@@ {{"a", "z"}, {"0", "9"}}], 6]

or

RandomSample[Join @@ (CharacterRange @@@ {{"a", "z"}, {"0", "9"}}), 6]

This guarantees no collisions because RandomSample selects elements without replacement.

$\endgroup$
  • $\begingroup$ How does does guarantee no collisions? $\endgroup$ – Moo Dec 13 '18 at 15:31
3
$\begingroup$

Inspired by some of the other answers and comments, here's a rather silly brute-force approach. We can RandomSample a range that we can use to enumerate all combinations.

range = Range[0, 36^6 - 1];
(* This takes a little while: 15 seconds on my laptop. *)

chars = Union[CharacterRange["a", "z"], CharacterRange["0", "9"]];

makeString[n_] := ToString@Part[chars, 1 + IntegerDigits[n, 36, 6]];

Then

makeString /@ RandomSample[range, 1000]

will always return a bunch of unique strings.

$\endgroup$
  • 2
    $\begingroup$ This becomes much less silly if you use RandomSample[0 ;; 36^6 - 1, 1000] instead. This way, the humongous list range need not be created and 1000 words are created within 4 ms. See also Carl's answer. $\endgroup$ – Henrik Schumacher Dec 13 '18 at 21:56
  • $\begingroup$ Holy cow I had no idea that worked! $\endgroup$ – Pillsy Dec 13 '18 at 23:34
2
$\begingroup$

Following is what you want. Unfortunately it takes time to generate all possible set for n=6. But for n=5 it works. And it is guaranteed that there is no repeated element.

val = Tuples[Join @@ (CharacterRange @@@ {{"A", "Z"}, {"0", "9"}}), 5];

    RandomSample[val, 5]

Much smart way is

DeleteDuplicates[
 Table[RandomSample[
   Join @@ (CharacterRange @@@ {{"A", "Z"}, {"0", "9"}}), 6], 5]]

It is very unlikely to generate the same element.

n = 10000;
Length@DeleteDuplicates[
   Table[RandomSample[
     Join @@ (CharacterRange @@@ {{"A", "Z"}, {"0", "9"}}), 6], n]] ==
  n

True

But when you increase n

Table[n = 100000;
  n - Length@
    DeleteDuplicates[
     Table[RandomSample[
       Join @@ (CharacterRange @@@ {{"A", "Z"}, {"0", "9"}}), 6], n]],
   10] // Max

5

This means 5 elements are repeated when we generate 100000 sample.. Of course, it might be larger than 5.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.