How to code all possible combinations of string?

Question

Lets say I have String word = "hello12".

I need to have all possible combinations of special characters instead of numbers (characters I get when use shift+number). So, the result I want to get is hello12, hello!2, hello1@, hello!@.

What I did is created switch with all cases (1 = '!', 2 = '@'...) but I can't get how to code all the combinations. All I could code is change all the numbers with special symbols (code is below)

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

Cristian Mocanu · Answer 1 · 2019-10-08T12:04:35.850

Building on the code from: Generate All Possible Combinations - Java, I've come up with this implementation that does what you need. It will find the index of all digits in your string and then generate all possibilities in which they can be replaced with the special characters.

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

score 1 · Accepted Answer · answered Oct 08 '19 at 11:58

Theory

Combinatory is often easier to express with recursive methods (methods that call themselves).

I think that the algorithm is more understandable with an example so let's take String word = hello12.

We will iterate on each character until a digit is found. The first one is 1. At this point, we can imagine the word been split in two by a virtual cursor:

hello is on the left side. We know that it won't change.
12 is on the right side. Each character is likely to be a digit and thus to change.

To retrieve all the possible combinations, we want to:

Keep the first part of the word
Compute all the possible combinations of the second part of the word
Append each of these combinations to the first part of the word

The following tree represents what we want to compute (the root is the first part of the word, each branch represent a combination)

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

You want to write an algorithm that gathers all the branches of this tree.

Java Code

/!\ I advise you to try to implement what I described above before taking a look at the code: that's how we improve ourselves!

Here is the corresponding Java code:

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

Please leave a comment if you want me to explain the algorithm further.

How to code all possible combinations of string?

2 Answers2

Theory

Java Code