Алгоритм для генерации всех вариантов слова

Question

Я хотел бы объяснить свою проблему на следующем примере.

принять слово: abc a имеет варианты: ä,
b не имеет вариантов.
с имеют варианты: ç

поэтому возможные слова:

а
AbC
AbC
AbC
AbC
AbC

теперь я ищу алгоритм, который печатает все варианты слов для абстракции слов с помощью арбитражных буквенных переменных.

Answer 1

Я бы порекомендовал вам решить эту проблему рекурсивно. Вот некоторые Java-код для вас, чтобы начать работу:

static Map<Character, char[]> variants = new HashMap<Character, char[]>() {{ 
    put('a', new char[] {'ä', 'à'}); 
    put('b', new char[] {  }); 
    put('c', new char[] { 'ç' }); 
}}; 

public static Set<String> variation(String str) { 

    Set<String> result = new HashSet<String>(); 

    if (str.isEmpty()) { 
     result.add(""); 
     return result; 
    } 

    char c = str.charAt(0); 
    for (String tailVariant : variation(str.substring(1))) { 
     result.add(c + tailVariant); 
     for (char variant : variants.get(c)) 
      result.add(variant + tailVariant); 
    } 

    return result; 
} 

Тест:

public static void main(String[] args) { 
    for (String str : variation("abc")) 
     System.out.println(str); 
} 

Выход:

abc 
àbç 
äbc 
àbc 
äbç 
abç 

Answer 2

Общая часть:

string[] letterEquiv = { "aäà", "b", "cç", "d", "eèé" }; 

// Here we make a dictionary where the key is the "base" letter and the value is an array of alternatives 
var lookup = letterEquiv 
    .Select(p => p.ToCharArray()) 
    .SelectMany(p => p, (p, q) => new { key = q, values = p }).ToDictionary(p => p.key, p => p.values); 

Рекурсивный вар записанный на C#.

List<string> resultsRecursive = new List<string>(); 

// I'm using an anonymous method that "closes" around resultsRecursive and lookup. You could make it a standard method that accepts as a parameter the two. 
// Recursive anonymous methods must be declared in this way in C#. Nothing to see. 
Action<string, int, char[]> recursive = null; 
recursive = (str, ix, str2) => 
{ 
    // In the first loop str2 is null, so we create the place where the string will be built. 
    if (str2 == null) 
    { 
     str2 = new char[str.Length]; 
    } 

    // The possible variations for the current character 
    var equivs = lookup[str[ix]]; 

    // For each variation 
    foreach (var eq in equivs) 
    { 
     // We save the current variation for the current character 
     str2[ix] = eq; 

     // If we haven't reached the end of the string 
     if (ix < str.Length - 1) 
     { 
      // We recurse, increasing the index 
      recursive(str, ix + 1, str2); 
     } 
     else 
     { 
      // We save the string 
      resultsRecursive.Add(new string(str2)); 
     } 
    } 
}; 

// We launch our function 
recursive("abcdeabcde", 0, null); 

// The results are in resultsRecursive 

нерекурсивную версия

List<string> resultsNonRecursive = new List<string>(); 

// I'm using an anonymous method that "closes" around resultsNonRecursive and lookup. You could make it a standard method that accepts as a parameter the two. 
Action<string> nonRecursive = (str) => 
{ 
    // We will have two arrays, of the same length of the string. One will contain 
    // the possible variations for that letter, the other will contain the "current" 
    // "chosen" variation of that letter 
    char[][] equivs = new char[str.Length][]; 
    int[] ixes = new int[str.Length]; 

    for (int i = 0; i < ixes.Length; i++) 
    { 
     // We start with index -1 so that the first increase will bring it to 0 
     equivs[i] = lookup[str[i]]; 
     ixes[i] = -1; 
    } 

    // The current "workin" index of the original string 
    int ix = 0; 

    // The place where the string will be built. 
    char[] str2 = new char[str.Length]; 

    // The loop will break when we will have to increment the letter with index -1 
    while (ix >= 0) 
    { 
     // We select the next possible variation for the current character 
     ixes[ix]++; 

     // If we have exausted the possible variations of the current character 
     if (ixes[ix] == equivs[ix].Length) 
     { 
      // Reset the current character to -1 
      ixes[ix] = -1; 

      // And loop back to the previous character 
      ix--; 

      continue; 
     } 

     // We save the current variation for the current character 
     str2[ix] = equivs[ix][ixes[ix]]; 

     // If we are setting the last character of the string, then the string 
     // is complete 
     if (ix == str.Length - 1) 
     { 
      // And we save it 
      resultsNonRecursive.Add(new string(str2)); 
     } 
     else 
     { 
      // Otherwise we have to do everything for the next character 
      ix++; 
     } 
    } 
}; 

// We launch our function 
nonRecursive("abcdeabcde"); 

// The results are in resultsNonRecursive 

Оба прокомментирован.

Answer 3

Быстро взломанный решение в Python:

def word_variants(variants): 
    print_variants("", 1, variants); 

def print_variants(word, i, variants): 
    if i > len(variants): 
    print word 
    else: 
    for variant in variants[i]: 
     print_variants(word + variant, i + 1, variants) 

variants = dict() 
variants[1] = ['a0', 'a1', 'a2'] 
variants[2] = ['b0'] 
variants[3] = ['c0', 'c1'] 

word_variants(variants)