Algorithm to generate all variants

Question

I have a bit of a problem I have for example a word treasure

I am trying to find all the possible variants of this word possible only including letters and numbers a-z 0-9 that still look similar to the original word.

For example a couple of examples would be 7r345ur3 or 7rea5ure. I need all the possible outcomes I spent a very long time looking for the definitions of the terms, I found the term Leet which refers to replacing letters and numbers " L33t 5p34k "

The generators I found online are good at giving me 1 result but I need thousands.

I found this post ; Algorithm to generate all variants of a word

Which gave this JAVA code example in one of the answers;

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;
}

Would this code example achieve what I'm trying to accomplish ?

I have never touched JAVA but from the looks of it I can add and edit these lines;

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

with all the possible characters I want to use but would someone be kind enough to change this so that it applies this to the input word of Treasure.

I really hope what I'm trying to achieve is clear in the question.

If you've never programmed with Java before, then it is probably best to start with some more simple concepts and following some beginners Java tutorial. This site isn't really for writing code for you, it's for helping with specific problems you have had with your code. — Henry Twist
– Henry Twist, Commented Aug 1, 2021 at 18:03
To what end? You can make something which permutes the different possibilities using per-letter substitutions (a permuter), or you could also go backwards and turn substitutions into english letters for finding matching words (a filter). — Rogue
– Rogue, Commented Aug 1, 2021 at 22:10

Eritrean · Accepted Answer · 2021-08-01 21:40:55Z

1

The method you found is a so-called recursive method, a method that constantly calls itself until a certain condition is met. If you want to simply adapt it and use it for your purposes, just change the map so that each letter is assigned the corresponding digit if such a digit exists that can be used as a substitute for the letter. Otherwise leave the array empty. i.e.

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'});

This should give you the desired result. But it would be better if you also understand what is going on inside the method. Recursive methods can be hard to read and it is not obvious at first sight what is going on. You can try to implement the method iteratively.

If you are a java newbie and can't implement the algorithm to create all combinations yourself, you might want to use a library. Generex for example would be good fit for your task. Generex takes a regular expression and can return a random string matched to the expression or all possible strings matching the regular expression. A simple example to show the use of the library:

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);
    }
}

Output:

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

In the above example generex will create strings by taking one letter or digit from each charachter class (i.e. from each square bracket) and return a list of all possible combinations.

You can generalize the above to use any input instead of a fixed string like treasurein the above example. To do so, you need to create a map with each letter as key and the letter and possible substitution digits as value. Afterwards you just need to split your input at each char get the values for each letter from your map and pass those to generex. Something like below should get you started.

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();
    }
}

output:

13wi5

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

edited Aug 1, 2021 at 21:40

answered Aug 1, 2021 at 20:38

Eritrean

16.6k3 gold badges25 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Lewis Over a year ago

Thankyou honestly I really appreciate your detailed answer, That's amazing! You have really helped me I am very grateful would you be able to advise though when I run your code I get this package com.mifmif.common.regex does not exist import com.mifmif.common.regex.Generex; is this because I have not installed Generex? Do I need to install this separately, I apologize for the questions this would be the first JAVA application I have ran. I have installed the JDK and have saved your code as example.java I have then go to the command line and ran javac example.java this is when error

Eritrean Over a year ago

Are you using an IDE like eclipse, intelij or netbeans?

Lewis Over a year ago

I'll download intelij

Eritrean Over a year ago

Using an IDE makes a lot of things easier, like instead of compiling everything yourself and having to include required libraries manually.

Eritrean Over a year ago

It is not absolutely necessary but very convenient and you can fully focus on coding and get possible errors while writing instead of compiling. After installing Intelij, create a Maven project, go to Maven copy the dependency to your pom.xml. If you don't know what maven is just create a simple java project download the jar from the same link and add it to your classpath

|

score 0 · Accepted Answer · 2021-08-02 03:08:02Z

Try this.

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);
}

output:

size=128
treasure
treasur3
treasu2e
treasu23
 .....
72345u2e
72345u23

Collectives™ on Stack Overflow

Algorithm to generate all variants

2 Answers 2

6 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related