0

I am trying to find a quick way to get all possible permutations of a word. Right now I am Using Guava, but it kills my RAM for words with >10 characters. My current approach is:

List<String> list = new ArrayList();
for(char c : word.toCharArray()){
    list.add(String.valueOf(c));
}
Collection<List<String>> substrings = Collections2.orderedPermutations(list);

List<String> cleanedList = new ArrayList<>();

substrings.stream()
    .forEach(f-> {
        String concat = "";
        for(int i = 0; i < f.size(); i++){
            concat += f.get(i);
        }
        cleanedList.add(concat);
    });

The result is fine, e.g. for "Wei": enter image description here

Thats exactly what I want but I need it more efficiently. Is there a way? I mean I kind of get the problem as 4 characters gets 24 options and 7 characters already produces 840.. It probably be a good start to have a function that realizes if characters are the same and won't set a character in a position another character of the same type was already in.

AnanasXpress
  • 111
  • 1
  • 12
  • 2
    Why are you trying to store them in memory all at once? Why do you need that? – chrylis -cautiouslyoptimistic- Mar 22 '21 at 19:00
  • Isn't it 7! -> 5040 elements for 7 character string? And 10! -> 3628800 for 10 character one? If each one have 10 characters, each taking 2 bytes, that's like 80MB. Keeping anything more than that in memory isn't wise. Btw. keep in mind that String are immutable, whenever you append a character it actually creates a new object. You could use StringBuilder instead. – Amongalen Mar 22 '21 at 19:02
  • Depending on what you are trying to do you might want to make an iterator implementation, this makes it so you can generate the list as you need it and do not need to store all the permutations at the same time. – Pete Mar 22 '21 at 20:17
  • Great insight guys. I am returning all possibilities to compare them with a dictionary. I think I need to have an implementation that checks to even bother saving a permutation if it is not in the dictionary.. But it would still have to generate all possibilities.. – AnanasXpress Mar 22 '21 at 21:40

0 Answers0