Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Algorithm to generate all variants of a word
- 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ç
- 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)
- 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);
- 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
Add Comment
Please, Sign In to add comment