生成所有变体的算法

我有一个小问题,例如一个词 treasure

我试图找到这个词的所有可能变体,只包括看起来仍然与原始词相似的字母和数字 a-z 0-9

例如,有几个示例是 7r345ur37rea5ure。我需要所有可能的结果我花了很长时间寻找术语的定义,我发现术语 Leet 指的是替换字母和数字 " L33t 5p34k "

我在网上找到的生成器很擅长给我 1 个结果,但我需要数千个。

我找到了这篇文章; Algorithm to generate all variants of a word

在其中一个答案中给出了这个 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;
}

此代码示例能否实现我想要完成的任务?

我从未接触过 JAVA,但从它的外观来看,我可以添加和编辑这些行;

put('a','à'});
put('b',new char[] {        });
put('c',new char[] { 'ç'    });

我想使用所有可能的字符,但有人愿意改变它,以便将其应用于 Treasure 的输入词。

我真的希望我想要达到的目标在问题中很清楚。

bestd 回答:生成所有变体的算法

你找到的方法就是所谓的递归方法,就是不断调用自身直到满足某个条件的方法。如果您只想简单地调整它并将其用于您的目的,只需更改映射,以便为每个字母分配相应的数字(如果存在可用作该字母的替代品的数字)。否则将数组留空。即

put('a',new char[] {'4'});
put('b',new char[] {'8'});
put('c',new char[] {});
put('d',new char[] {});
put('e',new char[] {'3'});
put('f',new char[] {});
put('g',new char[] {'6'});
put('h',new char[] {'4'});
put('i',new char[] {'1'});
put('j',new char[] {});
put('k',new char[] {});
put('l',new char[] {'1'}");
....
put('y',new char[] {'9'});
put('z',new char[] {'2'});

这应该会给你想要的结果。但是如果您也了解方法内部发生的事情会更好。递归方法可能难以阅读,并且乍一看并不明显。您可以尝试迭代实现该方法。

如果您是 Java 新手并且无法实现自己创建所有组合的算法,您可能需要使用库。例如,Generex 非常适合您的任务。 Generex 采用正则表达式,可以返回与该表达式匹配的随机字符串或与该正则表达式匹配的所有可能字符串。一个简单的例子来展示库的使用:

import com.mifmif.common.regex.Generex;

public class Example {

    public static void main(String[] args) {
        Generex gen = new Generex("[t7][r2][e3][a4][s5][u][r2][e3]");
        gen.getAllMatchedStrings().forEach(System.out::println);
    }
}

输出:

72345u23
72345u2e
72345ur3
72345ure
7234su23
7234su2e
7234sur3
7234sure
723a5u23
....
trea5ure
treasu23
treasu2e
treasur3
treasure

在上面的示例中,generex 将通过从每个字符类(即从每个方括号)中获取一个字母或数字来创建字符串,并返回所有可能组合的列表。

您可以将上述内容概括为使用任何输入,而不是上面示例中的固定字符串(如 treasure)。为此,您需要创建一个映射,其中每个字母作为键,字母和可能的替代数字作为值。之后,您只需要在每个字符处拆分输入,从地图中获取每个字母的值并将其传递给generex。类似下面的内容应该可以帮助您入门。

import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

import com.mifmif.common.regex.Generex;

public class Example {
    private static final Map<String,String> MY_MAP = createMap();

    public static void main(String[] args) {
        String myString = "Lewis";

        String random = randomVariant(myString);
        System.out.println(random);
        System.out.println();

        List<String> variants = allVariants(myString);
        variants.forEach(System.out::println);
    }

    private static Map<String,String> createMap() {
        Map<String,String> result = new HashMap<>();
        result.put("a","[a4]");
        result.put("b","[b8]");
        result.put("c","[c]");
        result.put("d","[d]");
        result.put("e","[e3]");
        result.put("f","[f]");
        result.put("g","[g6]");
        result.put("h","[h4]");
        result.put("i","[i1]");
        result.put("j","[j]");
        result.put("k","[k]");
        result.put("l","[l1]");
        result.put("m","[m]");
        result.put("n","[n2]");
        result.put("o","[o0]");
        result.put("p","[p]");
        result.put("q","[q]");
        result.put("r","[r2]");
        result.put("s","[s5]");
        result.put("t","[t7]");
        result.put("u","[u]");
        result.put("v","[v]");
        result.put("w","[w]");
        result.put("x","[x]");
        result.put("y","[y9]");
        result.put("z","[z2]");

        return Collections.unmodifiableMap(result);
    }

    public static List<String> allVariants(String str){
        String reg = Pattern.compile("").splitAsStream(str.toLowerCase()).map(MY_MAP::get).collect(Collectors.joining());
        Generex gen = new Generex(reg);
        return gen.getAllMatchedStrings();
    }

    public static String randomVariant(String str){
        String reg = Pattern.compile("").splitAsStream(str.toLowerCase()).map(MY_MAP::get).collect(Collectors.joining());
        Generex gen = new Generex(reg);
        return gen.random();
    }
}

输出:

13wi5

13w15
13w1s
13wi5
13wis
1ew15
1ew1s
1ewi5
1ewis
l3w15
l3w1s
l3wi5
l3wis
lew15
lew1s
lewi5
lewis
,

试试这个。

static final String[] VARIANTS = {"t7","r2","e3","a4","s5","u"};
static final Map<Character,String> VARIANTS_MAP = Arrays.stream(VARIANTS)
        .collect(Collectors.toMap(s -> s.charAt(0),Function.identity()));

static Set<String> variation(String word) {
    int size = word.length();
    String[] array = word.chars()
        .mapToObj(c -> VARIANTS_MAP.get((char)c))
        .toArray(String[]::new);
    Set<String> result = new LinkedHashSet<>();
    char[] buffer = new char[size];
    new Object() {
        void gen(int index) {
            if (index >= size) {
                result.add(new String(buffer));
            } else {
                String s = array[index];
                for (int i = 0,max = s.length(); i < max; ++i) {
                    buffer[index] = s.charAt(i);
                    gen(index + 1);
                }
            }
        }
    }.gen(0);
    return result;
}

public static void main(String[] args) {
    Set<String> result = variation("treasure");
    System.out.println("size=" + result.size());
    result.forEach(System.out::println);
}

输出:

size=128
treasure
treasur3
treasu2e
treasu23
 .....
72345u2e
72345u23
本文链接:https://www.f2er.com/1038.html

大家都在问