Getting all permutations of a word where letters may have variants

i am looking for the pseudocode algorithm to the following problem.

i want to get all permutations of a word. in the alphabet each letter may have variants. for example in french the letter e can also be é è ê ë. the same with other letters... aàâä etc.

now for any given word i want to list all the possible permutations with all variants of all letters.

input is a word and a all letters and their variants if they开发者_开发百科 have some.

---

Here is some basic pseudocode:

  1. Generate a list Perm[1...n] of all permutations without considering variants.
  2. For i = 1 to n do
  3.  For j = 1 to |Perm[i]| do
  4.   For k = 1 to #variants(Perm[i][j])
  5.    print Perm[i][1...j-1] (variant #k) Perm[i][j+1...|Perm[i]|]

In words, generate the permuations without considering variants (a problem already treated several times on SO, look for "generating permutations"). Then, for each permutation, look at each letter and for each of its permutations, print the word with the letter replaced by its variant.