Как закодировать все возможные комбинации строк?

Question

Допустим, у меня есть String word = "hello12".

Мне нужно иметь все возможные комбинации специальных символов вместо цифр (символов, которые я получаю, когда использую shift + номер). Итак, результат, который я хочу получить: hello12, hello! 2, hello1 @, hello! @.

То, что я сделал, это созданный переключатель со всеми делами (1 = '!', 2 = '@'. ..) но я не могу понять, как закодировать все комбинации. Все, что я мог закодировать, это изменить все числа специальными символами (код ниже)

char[] passwordInCharArray;

        for(int i=0; i<passwordList.length; i++){
            for(int j = 0; j<passwordList[i].length(); j++){
                if(Character.isDigit((passwordList[i].charAt(j)))){
                    passwordInCharArray = passwordList[i].toCharArray();
                    passwordInCharArray[j] = getSpecialSymbol(passwordList[i].charAt(j));
                    passwordList[i]=String.valueOf(passwordInCharArray);
                }
            }
        }

Answer 1

Теория

Комбинаторный часто проще выразить с помощью рекурсивных методов (методы, которые сами себя вызывают).

Я думаю, что алгоритм более понятен на примере, поэтомудавайте возьмем String word = hello12.

Мы будем повторять каждый символ, пока не будет найдена цифра. Первый - 1. В этот момент мы можем представить, что слово было разделено на две части виртуальным курсором:

• hello находится слева. Мы знаем, что это не изменится.
• 12 на правой стороне. Каждый символ может быть цифрой и, следовательно, изменяться.

Чтобы извлечь все возможные комбинации, мы хотим:

1. Сохранить первую часть слова
2. Вычислить все возможные комбинации второй части слова
3. Добавить каждую из этих комбинаций к первой части слова

Следующее дерево представляет то, что мыхотите вычислить (корень - первая часть слова, каждая ветвь представляет комбинацию)

hello
├───1
│   ├───2 (-> hello12)
│   └───@ (-> hello1@)
└───!
    ├───2 (-> hello!2)
    └───@ (-> hello!@)

Вы хотите написать алгоритм, который собирает все ветви этого дерева.

Java Code

/! \ Я советую вам попытаться реализовать то, что я описал выше, прежде чем взглянуть на код: вот как мы улучшаем себя!

Вотсоответствующий код Java:

public static void main(String[] args) {
    Set<String> combinations = combinate("hello12");
    combinations.forEach(System.out::println);
}

public static Set<String> combinate(String word) {
    // Will hold all the combinations of word
    Set<String> combinations = new HashSet<String>();

    // The word is a combination (could be ignored if empty, though)
    combinations.add(word);

    // Iterate on each word's characters
    for (int i = 0; i < word.toCharArray().length; i++) {
        char character = word.toCharArray()[i];

        // If the character should be replaced...
        if (Character.isDigit(character)) {

            // ... we split the word in two at the character's position & pay attention not be exceed word's length  
            String firstWordPart = word.substring(0, i);
            boolean isWordEnd = i + 1 >= word.length();
            String secondWordPart = isWordEnd ? "" : word.substring(i + 1);

            // Here is the trick: we compute all combinations of the second word part... 
            Set<String> allCombinationsOfSecondPart = combinate(secondWordPart);

            // ... and we append each of them to the first word part one by one
            for (String string : allCombinationsOfSecondPart) {
                String combination = firstWordPart + getSpecialSymbol(character) + string;
                combinations.add(combination);
            }
        }
    }
    return combinations;
}

Пожалуйста, оставьте комментарий, если вы хотите, чтобы я объяснил алгоритм дальше.

Answer 2

Опираясь на код из: Генерация всех возможных комбинаций - Java , я пришел к этой реализации, которая делает то, что вам нужно. Он найдет индекс всех цифр в вашей строке и затем сгенерирует все возможности, в которых они могут быть заменены специальными символами.

import java.util.*;

public class Comb {

    public static List<String> combinations(String pass) {
        String replace = ")!@#$%^&*(";
        char[] password = pass.toCharArray();
        List<Integer> index = new ArrayList<Integer>();
        List<String> results = new ArrayList<String>();
        results.add(pass);

        //find all digits
        for (int i = 0; i < password.length; i++) {
            if (Character.isDigit(password[i])) {
                index.add(i);
            }
        }

        //generate combinations
        int N = (int) Math.pow(2d, Double.valueOf(index.size()));  
        for (int i = 1; i < N; i++) {
            String code = Integer.toBinaryString(N | i).substring(1);
            char[] p = Arrays.copyOf(password, password.length);

            //replace the digits with special chars
            for (int j = 0; j < index.size(); j++) {
                if (code.charAt(j) == '1') {
                    p[index.get(j)] = replace.charAt(p[index.get(j)] - '0');
                }
            }
            results.add(String.valueOf(p));
        }
        return results;
    }

    public static void main(String... args) {
        System.out.println(combinations("hello12"));
    }
}