I’m writing an app that does something like a custom number (license) plate generator tool where if I ask for the plate “robin” it will suggest I try:
- r0bin
- rob1n
- r0b1n
Are there any published algorithms which can do this? It has to be able to handle replacing single letters with multiples, e.g. m with rn and vise-versa and not fall over if it replaces an i with an l then comes to check the l and replaces it back to an i.
The list of what gets swapped with what is going to be user input but I’m not expecting a huge list, possibly 10 pairs at most.
I’ll be implementing this in Ruby or Python but I should be able to convert code from any other language.
1
First, you get a list of replacements that it would make:
- I –> 1
- A –> 4
- m –> rn
- etc…
You will have some finite set of these changes.
For that set, generate the set of combinations. If you have 10 changes, there are possibly 1024 changes total. This list is all the changes from 0 .. 1023. Take the bit representation of each of these values. The 953rd (1110111001) change would have the first, second, third, fifth, sixth, seventh, and tenth change applied.
This could be reduced by only having changes that have a candidate letter in them (it would not make sense to try to apply the change ‘m’ –> ‘rn’ when there is not an ‘m’ in ‘robin’).
1
Based on my understanding of your requirements, I am not aware of a published algorithm specifically for your case, but you can make one using the following discussion.
I will use an odd example, but you will see why soon.
Let us say you have a string such as
AB1C4D6
Assume that:
Character in position 3 can have values (1,2,3), that is 3 distinct values.
Character in position 5 can have values (4,5), that is 2 distinct values.
Character in position 7 can have values (6,7), that is 2 distinct values.
Possible outcomes of performing various replace operaiotns on the original string are shown below.
The total number of strings we can obtain is 3x2x2 = 12 (including the initial string).
This process is similar to generating Cartesian product of 3 sets (like SELECT * FROM T1, T2, T3).
Given a string length of N letters, if each letter i has at most r_i possible replacement characters, then we’d have a total of (r_0*r_1*r_2*…*r_N) words where r_i=1 if there are no replacements for the letter.
The reason I have choosen this specific example is that there is a description on how to generate the Cartisian product in here that uses similar values, so it would be easy for you to follow (although it is not in either Ruby or Python).
The concept will be the same if you map 1 input character to more than 1 character as long as make a single pass to the string and use the appropriate function to perform the replace.