3

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

    }
}
Community
  • 1
  • 1
COYG
  • 1,538
  • 1
  • 16
  • 31

4 Answers4

4
    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.

Compass
  • 5,867
  • 4
  • 30
  • 42
  • Wow. Such an easy fix, cheers mate. Tested it and worked just how I wanted even without duplicates. Will accept as answer when it lets me in a couple of minutes. – COYG Jun 22 '16 at 19:22
3

One way to think about this problem is to consider all binary combinations of the given set.

For example, if the set in question is {a, b, c}, then all the binary combinations (2^3 = 8) are:

000 = {}
001 = {c}
010 = {b}
011 = {b,c}
100 = {a}
101 = {a, c}
110 = {a, b}
111 = {a, b, c}

Once you build these sets, you can use recursion to get the combinations of each set.

Michael Markidis
  • 4,163
  • 1
  • 14
  • 21
  • You only provide combinations, he also wants permutations. For each combination, which is an excellent approach btw, he will need to permute each of these. – Grayson Jun 22 '16 at 19:26
  • @Grayson I mention that the recursion can then be used on each combination. – Michael Markidis Jun 22 '16 at 19:27
  • @ Michael Markidis I see that now. I love the binary approach. I have used it in various solutions. – Grayson Jun 22 '16 at 19:30
0

Powerset will not return you what you want. This is because the set {a, b, c} is equivalent to {b, a, c} and for other sets that you want to have.

You can modify your algorithm to create all possible permutations from each of the set. This will give you some of the duplicates, so you can store them in the set.

Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
-1
public class Stringpermutations {
    public static void main(String[] args) {
        permutations(0,"123");
    }

    public static void permutations(int start, String s) {
        char[] chr=s.toCharArray();
        if(start==s.length()) {
            System.out.println(s);
        }
        for(int i=start;i<s.length();i++) {
            char c=chr[i];
            chr[i]=chr[start];
            chr[start]=c;
            permutations(start+1,new String(chr));
        } 
    }
}
Valentin Michalak
  • 2,089
  • 1
  • 14
  • 27
Vasista TVN
  • 285
  • 3
  • 6