COYG COYG - 5 months ago 19
Java Question

Finding all possible combinations within a String using permutation

I currently have two methods which uses recursion to give me all of the possible combinations of a given

String
, I got to this with the help of this answer. So if I entered the
String
and it returns these combinations:

and
adn
dan
dna
nad
nda


However I want it to return all possible combinations of the rest of even one/two letters in that string like so:

a
n
d
an
ad
na
nd
etc...


Something like this answer but in java

That answer also mentioned and linked Powersets which showed all possible subsets of a,b,c:

Image

As you can see it doesn't do the combinations back to front such as

c,b,a
c,a,b
c,a
....


Here's the current code I have where I would like to implement this:

public void permutation(String str) {

permutation("", str);
}

private void permutation(String prefix, String str) {

int n = str.length();
if (n == 0) myList.add(prefix);
else {
for (int i = 0; i < n; i++)

permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));

}
}

Answer
    if (n == 0) myList.add(prefix);

This statement you've provided only adds it if you've permuted all characters available in str.

If you remove the if (n == 0) it'll add all the prefixes from a to an to and, so you would instead use:

private void permutation(String prefix, String str) {
    int n = str.length();
    myList.add(prefix);
    if(n > 0) {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));

    }

You'll obviously get a bunch of duplicates and possibly an empty string as a result of the recursion, but there is a Collection you can use that doesn't allow duplicates, or you can check if it is a duplicate before adding. I'll leave the optimization up to you.