daily pastebin goal
59%
SHARE
TWEET

Untitled

a guest Aug 19th, 2018 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Algorithm to generate all variants of a word
  2. static Map<Character, char[]> variants = new HashMap<Character, char[]>() {{
  3.     put('a', new char[] {'ä', 'à'});
  4.     put('b', new char[] {        });
  5.     put('c', new char[] { 'ç'    });
  6. }};
  7.  
  8. public static Set<String> variation(String str) {
  9.  
  10.     Set<String> result = new HashSet<String>();
  11.  
  12.     if (str.isEmpty()) {
  13.         result.add("");
  14.         return result;
  15.     }
  16.  
  17.     char c = str.charAt(0);
  18.     for (String tailVariant : variation(str.substring(1))) {
  19.         result.add(c + tailVariant);
  20.         for (char variant : variants.get(c))
  21.             result.add(variant + tailVariant);
  22.     }
  23.  
  24.     return result;
  25. }
  26.    
  27. public static void main(String[] args) {
  28.     for (String str : variation("abc"))
  29.         System.out.println(str);
  30. }
  31.    
  32. abc
  33. àbç
  34. äbc
  35. àbc
  36. äbç
  37. abç
  38.    
  39. def word_variants(variants):
  40.   print_variants("", 1, variants);
  41.  
  42. def print_variants(word, i, variants):
  43.   if i > len(variants):
  44.     print word
  45.   else:
  46.     for variant in variants[i]:
  47.       print_variants(word + variant, i + 1, variants)
  48.  
  49. variants = dict()
  50. variants[1] = ['a0', 'a1', 'a2']
  51. variants[2] = ['b0']
  52. variants[3] = ['c0', 'c1']
  53.  
  54. word_variants(variants)
  55.    
  56. string[] letterEquiv = { "aäà", "b", "cç", "d", "eèé" };
  57.  
  58. // Here we make a dictionary where the key is the "base" letter and the value is an array of alternatives
  59. var lookup = letterEquiv
  60.     .Select(p => p.ToCharArray())
  61.     .SelectMany(p => p, (p, q) => new { key = q, values = p }).ToDictionary(p => p.key, p => p.values);
  62.    
  63. List<string> resultsRecursive = new List<string>();
  64.  
  65. // 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.
  66. // Recursive anonymous methods must be declared in this way in C#. Nothing to see.
  67. Action<string, int, char[]> recursive = null;
  68. recursive = (str, ix, str2) =>
  69. {
  70.     // In the first loop str2 is null, so we create the place where the string will be built.
  71.     if (str2 == null)
  72.     {
  73.         str2 = new char[str.Length];
  74.     }
  75.  
  76.     // The possible variations for the current character
  77.     var equivs = lookup[str[ix]];
  78.  
  79.     // For each variation
  80.     foreach (var eq in equivs)
  81.     {
  82.         // We save the current variation for the current character
  83.         str2[ix] = eq;
  84.  
  85.         // If we haven't reached the end of the string
  86.         if (ix < str.Length - 1)
  87.         {
  88.             // We recurse, increasing the index
  89.             recursive(str, ix + 1, str2);
  90.         }
  91.         else
  92.         {
  93.             // We save the string
  94.             resultsRecursive.Add(new string(str2));
  95.         }
  96.     }
  97. };
  98.  
  99. // We launch our function
  100. recursive("abcdeabcde", 0, null);
  101.  
  102. // The results are in resultsRecursive
  103.    
  104. List<string> resultsNonRecursive = new List<string>();
  105.  
  106. // 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.
  107. Action<string> nonRecursive = (str) =>
  108. {
  109.     // We will have two arrays, of the same length of the string. One will contain
  110.     // the possible variations for that letter, the other will contain the "current"
  111.     // "chosen" variation of that letter
  112.     char[][] equivs = new char[str.Length][];
  113.     int[] ixes = new int[str.Length];
  114.  
  115.     for (int i = 0; i < ixes.Length; i++)
  116.     {
  117.         // We start with index -1 so that the first increase will bring it to 0
  118.         equivs[i] = lookup[str[i]];
  119.         ixes[i] = -1;
  120.     }
  121.  
  122.     // The current "workin" index of the original string
  123.     int ix = 0;
  124.  
  125.     // The place where the string will be built.
  126.     char[] str2 = new char[str.Length];
  127.  
  128.     // The loop will break when we will have to increment the letter with index -1
  129.     while (ix >= 0)
  130.     {
  131.         // We select the next possible variation for the current character
  132.         ixes[ix]++;
  133.  
  134.         // If we have exausted the possible variations of the current character
  135.         if (ixes[ix] == equivs[ix].Length)
  136.         {
  137.             // Reset the current character to -1
  138.             ixes[ix] = -1;
  139.  
  140.             // And loop back to the previous character
  141.             ix--;
  142.  
  143.             continue;
  144.         }
  145.  
  146.         // We save the current variation for the current character
  147.         str2[ix] = equivs[ix][ixes[ix]];
  148.  
  149.         // If we are setting the last character of the string, then the string
  150.         // is complete
  151.         if (ix == str.Length - 1)
  152.         {
  153.             // And we save it
  154.             resultsNonRecursive.Add(new string(str2));
  155.         }
  156.         else
  157.         {
  158.             // Otherwise we have to do everything for the next character
  159.             ix++;
  160.         }
  161.     }
  162. };
  163.  
  164. // We launch our function
  165. nonRecursive("abcdeabcde");
  166.  
  167. // The results are in resultsNonRecursive
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top