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

well, you can write an algorithm to write all the substrings and then you can reverse all of them and add into your list. — Leo
– Leo, Commented Aug 26, 2014 at 1:58
but "ten" is not exactly a substring, although you can get this word just reusing the same letters that are present your string — Leo
– Leo, Commented Aug 26, 2014 at 2:01
@Leo "ten" is not a subtring??? What is it called then? And how would I add it to my arrayList? — Kaylo17
– Kaylo17, Commented Aug 26, 2014 at 2:07
@Kaylo17 it's called "string" right because it's a sequence of letters. So we can say "ent" is a substring of "environment", but "ten" is not. If you also want to get values such as "ten" given a string like "environment", what you're looking for (it seems to me) are the permutations of the letters that are present in the word "environment" — Leo
– Leo, Commented Aug 26, 2014 at 2:10

Mateusz Dymczyk · Accepted Answer · 2014-08-26 03:23:31Z

2

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.

edited Aug 26, 2014 at 3:23

answered Aug 26, 2014 at 2:16

Mateusz Dymczyk

15.2k10 gold badges63 silver badges94 bronze badges

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

4 Comments

Kaylo17 Over a year ago

I think this is exactly what I'm looking for. I'll write out the function and post it. I'm not worried about time complexity right and efficiency since this is mostly for learning purpose

PM 77-1 Over a year ago

@Kaylo17 - Do not forget to eliminate all duplicates, possibly by converting your list to set and back.

Mateusz Dymczyk Over a year ago

@PM77-1 fair point, my algorithm is very naive in that regard btu since he doesn't mind the time complexity I guess it's not a problem.

Kaylo17 Over a year ago

@MateuszDymczyk okay, So after a bit of work, I came up with this program. pastebin.com/hzknuhac . If you have time, could you tell me how to improve it or make it more efficient. I also realized that for words longer than 9 letters, I get an Out of memory exception

Community · Accepted Answer · 2017-05-23 12:05:02Z

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.

edited May 23, 2017 at 12:05

CommunityBot

11 silver badge

answered Aug 26, 2014 at 4:09

pimaster

1,96710 silver badges14 bronze badges

3 Comments

Kaylo17 Over a year ago

It works a lot better than the one I created. Thanks a lot. It still has an out of memory exception when I put in more than 7 characters though. I'll find a way to fix that though. Thanks again.

pimaster Over a year ago

The problem will be holding onto such a large list of string. You can pass in a consumer and handle each string as it is generated. An interesting task would be to break this task up over multiple threads.

Kaylo17 Over a year ago

It sounds like an interesting way to do it. I'll try and work on it over the next few hours and see what i can come up with

Yagnik Fadadu · Accepted Answer · 2022-08-13 06:51:26Z

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

Collectives™ on Stack Overflow

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

3 Answers 3

4 Comments

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related