COYG - 1 year ago 75
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
dan
dna
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
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:

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();
else {
for (int i = 0; i < n; i++)

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

}
}
``````

``````    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();
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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download