Creates all possible permutations of a string and its substrings

I want to improve this code to efficiently create all possible permutations/combinations of a string. For example, if I have the string "abc", the result would be the list [ab, ac, ba, bc, ca, cb, abc, acb ...]. I have a solution for this but it takes too long on larger inputs. I need help with improving its efficiency and speed.

The working code is below that I want to improve. Here's what it's doing:

It takes the input string and keeps adding the permutations to the permutations list. It loops through that list until the end. In the loop, it keeps adding new permutations to the permutations list so it keeps growing until we don't have any more permutations left and eventually, we reach the end of the list.

Example:

We have "abc" as the input string.

permutations list initialized to [a, b, c].

What the loop does

• a * bc -> ab, ac ('a' is permutaions[i] and 'bc' is what getMultiplicand(...) returned)

permutations -> [a, b, c, ab, ac]

• b * ac -> ba, bc

permutations -> [a, b, c, ab, ac, ba, bc]

• c * ab -> ca, cb

permutations -> [a, b, c, ab, ac, ba, bc, ca, cb]

• ab * c -> abc

permutations -> [a, b, c, ab, ac, ba, bc, ca, cb, abc]

• ac * b -> acb

permutations -> [a, b, c, ab, ac, ba, bc, ca, cb, abc, acb]

And so on...

At the end of the loop permutations is converted to a Set containing all unique possible combinations of the input string.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public class Test {

private Set<String> permute(String charSeq) {
long starttime = System.nanoTime();
List<String> permutations = new ArrayList<>();
// Add each character from the string to get us going for multiplication. We'll remove them at the very end.
for (int i = 0; i < charSeq.length(); i++) {
}
// This list will be used to hold the permutations produced by each iteration.
List<String> tempPermutation = new ArrayList<>();
for (int i = 0; i < permutations.size(); i++) {
Character[] multiplicand = getMultiplicand(charSeq, permutations.get(i));
for (Character character: multiplicand) {
}
// Merge the temporary permutations list with the main permutations list and then clear it for the next iteration.
tempPermutation.clear();
}
// Remove the single characters we added at the very beginning
for (int i = 0; i < charSeq.length(); i++) {
permutations.remove(String.valueOf(charSeq.charAt(i)));
}
// Convert the permutations list into a set to remove all the duplicates.
return new HashSet<>(permutations);
}

private Character[] getMultiplicand(String s, String toRemove) {
List<Character> characters = s.chars().mapToObj(c -> (char) c).collect(Collectors.toList());
for (int i = 0; i < toRemove.length(); i++) {
characters.remove(Character.valueOf(toRemove.charAt(i)));
}
return characters.toArray(new Character[0]);
}
}


P.S. This is my first post so tell me how it can be improved. Thanks.

Permutations are the kind of problem that quickly generate an incredible amount of data. Collecting them all into a "big bag" before returning them all at once becomes unfeasible. Instead use a simple producer-consumer design pattern: pass an instance of Consumer<String> as a parameter to the method and whenever you have a permutation ready, call the consumer immediately and let them handle the processing and storage of the reults.