Java - Get All Permutations, Substrings and Permutations of every Substring of a String

Question

Firstly, I'll start off by saying English is not my first language so I apologize for any poor explanations.

I want to know how to get every single substring of a String with so many different orders. Before you tell me this question has been asked before, I want to say that almost every code implementation of this task I see does not include duplicates. But Say I had a string "enviroment" and I wanted every single substring including "ment", "met", "ten", "net","note", "more" e.t.c e.t.c how would I acheive this??

This is the function I wrote.

     public static ArrayList<String> getAllSubstringsOfAString(String inputString)
     {
     ArrayList<String> allSubstrings = new ArrayList<String>();
     String sub;
     for(int i = 0; i < inputString.length(); i++)
     {
        for (int j = 1; j <= inputString.length() - i; j++)
        {
            sub = inputString.substring(i , i + j);
            allSubstrings.add(sub);
        }
      }
      return allSubstrings;
     }

When I run this function

    public static void main(String[] args) throws IOException {
    ArrayList<String> allSubStrings = getAllSubstringsOfAString("environment");
    for (String allSubString : allSubStrings) {
        System.out.println(allSubString);
    }

it prints this out

    e
    en
    env
    envi
    envir
    enviro
    environ
    environm
    environme
    environmen
    environment
    n
    nv
    nvi
    nvir
    nviro
    nviron
    nvironm
    nvironme
    nvironmen
    nvironment
    v
    vi
    vir
    viro
    viron
    vironm
    vironme
    vironmen
    vironment
    i
    ir
    iro
    iron
    ironm
    ironme
    ironmen
    ironment
    r
    ro
    ron
    ronm
    ronme
    ronmen
    ronment
    o
    on
    onm
    onme
    onmen
    onment
    n
    nm
    nme
    nmen
    nment
    m
    me
    men
    ment
    e
    en
    ent
    n
    nt
    t

Which is only a small part of what I want. I want the function to be able to get substrings in every order. For example, If I wanted it to include Strings like "net", "ten", "never" e.t.c, as they are all substrings of the word "environment". What changes do I have to make on my function to attain this?

Also, as I am a Java beginner, I would like to know If my code is well written and what changes I can make to my code to make it perform better and look better, and to follow common Java coding conventions.

Thanks in advance

Answer 1

1) generate all substrings (you got that part already)

2) for each substring generate all it's permutations - you can do it either recursively or iteratively using a bitvector (it's been shown here on SO how to do it, a quick google search will also give you some hints)

3) add all to the final list, this will get you what you already have, reversed version of what you have and all other permutations

For example with "abc" you will get:

• a (1 char, 1 permutation)
• ab (substring)
  • ba (substring permutation)
• abc (substring)
  • bca (substring permutation)
  • bac (substring permutation)
  • acb (substring permutation)
  • cab (substring permutation)
  • cba (substring permutation)

Be aware it might take some time to compute, when a string has N it has N! permutations and you will be calling it for each substring so N times which will yield O(N*N!) time complexity.

As @PM77-1 pointed out this might do a lot of unnecessary work if our string has duplicated substrings like abcabc. In that case before each new iteration you can check if the given substring is already in the set (yes, you change the resulting list to a set which has O(1) lookups) and skip it if it's already there.

Answer 2

With a bit of help from this other question, I threw this together.

public static void main(String[] args) {
    List<String> list = perms("codes");
    list.forEach(s -> System.out.println(s));
}

public static List<String> perms(String string) {

    List<String> result = new ArrayList<String>();
    char[] values = string.toCharArray();
    for (int width = 1; width <= values.length; width++) { // for every length
        int stack[] = new int[width];
        for (int i = 0; i < stack.length; i++) { // start from a specific point without duplicates
            stack[i] = stack.length - i - 1;
        }
        int position = 0;
        while (position < width) {

            position = 0;
            StringBuilder sb = new StringBuilder();
            while (position < width) { // build the string
                sb.append(values[stack[position]]);
                position++;
            }
            result.add(sb.toString());
            position = 0;
            while (position < width) {
                if (stack[position] < values.length - 1) {
                    stack[position]++;
                    if (containsDuplicate(stack) == false)
                        break;
                    else
                        position = 0;
                } else {
                    stack[position] = 0;
                    position++;
                }
            }
        }
    }
    return result;
}

private static boolean containsDuplicate(int[] stack) {
    for (int i = 0; i < stack.length; i++) {
        for (int j = 0; j < stack.length; j++) {
            if (stack[i] == stack[j] && i != j) {
                return true;
            }
        }
    }
    return false;
}

It doesn't re-use letter from the word unless the word contains the letter twice.
In which case there would be doubles.
It doesn't use recursion so stack overflow won't be a problem.

Answer 3

The Program below returns all possible sub set and their respective permutations.

• For example for value abcd@1234 it will return 986410 possible values from it.
• [Note]: it will work differently with permutations containing same characters.
  Example for value aaaa@1234 it will return 6850 possible values from it.

public class PermutationWithSub {
    public void subStrings(String string){
        List<List<Character>> listList = new ArrayList<>();
        listList.add(new ArrayList<>());
        ArrayList<String> subStringArraylist = new ArrayList<>();
        ArrayList<String> bruteList = new ArrayList<>();
        for (char c:string.toCharArray()){
            int size = listList.size();
            for (int i=0;i<size;i++){
                List<Character> temp = new ArrayList<>(listList.get(i));
                temp.add(c);
                listList.add(temp);
            }
        }
        for (List<Character> characterList : listList) {
            StringBuilder stringBuilder = new StringBuilder();
            for (Character character : characterList) {
                stringBuilder.append(character);
            }
            subStringArraylist.add(stringBuilder.toString());
        }
        for (String str:subStringArraylist){
            List<List<Character>> listListChar = permute(str);
            for (List<Character> listChar:listListChar){
                StringBuilder stringBuilder = new StringBuilder();
                for (Character character:listChar){
                    stringBuilder.append(character);
                }
                bruteList.add(stringBuilder.toString());
            }
        }
        listList.clear();
        subStringArraylist.clear();
        for (String str:bruteList){
                System.out.println(str);
        }
    }
    public List<List<Character>> permute(String string){
        List<List<Character>> powerSet = new ArrayList<>();
        generateSet(powerSet,new ArrayList<>(),string.toCharArray());
        return powerSet;
    }

    private void generateSet(List<List<Character>> powerSet, List<Character> temp, char[] chars) {
        if (temp.size()==chars.length){
            powerSet.add(new ArrayList<>(temp));
        }else {
            for (char aChar : chars) {
                if (temp.contains(aChar))
                    continue;
                temp.add(aChar);
                generateSet(powerSet, temp, chars);
                temp.remove(temp.size() - 1);
            }
        }
    }
    public static void main(String[] args) {
        MyBruteForceTool myBruteForceTool = new MyBruteForceTool();
        myBruteForceTool.subStrings("abcd@1234");
    }
}