doing a full permutation search and replace on a string

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.

-
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

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

-
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

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.

-