Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
2  
You haven't really defined the rules of replacement; you've merely given an example that hints at L33t speak. Once you understand your rules for substitution (and updated your question), the community will be in a better position to help you. –  GlenH7 Nov 21 '12 at 23:13
add comment

2 Answers 2

up vote 1 down vote accepted

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').

share|improve this answer
    
I like this solution. I have a feeling I'll initially implement it really inefficiently but then optimize it once it works. I think even unoptimized though it will be quick enough that no one will notice. –  Digininja Nov 22 '12 at 11:01
add comment

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.

enter image description here

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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