String Permutations Java

Question

I need to get all of the permutations of a string, but with a twist. I need to get the permutations, but at different lengths. Like this: the permutations of AB would be:

A

B

AA

BB

AB

BA

I can get the permutations of a string, with fixed lengths, but I'm stuck on this.

Why don't you put your solution in a loop with a length from 0 to your string's length ? — Denys Séguret, Sep 25 '12 at 20:22
I would modify @dystroy to include a maximum length, since you may not want to be limited to the length of the input String. — Code-Apprentice, Sep 25 '12 at 20:25
Are characters different in the string or there's repetitions? — Roman C, Sep 25 '12 at 20:29
It looks to me like this is multicombination, not permutation. Take a look at the algorithm [here](http://www.martinbroadhurst.com/combinatorial-algorithms.html#multicombinations). Just rerun the algorithm with different string lengths via a `for` loop. The algorithm itself is very much like counting. See [my answer to this question](http://stackoverflow.com/a/12288895/646634). — Brian, Sep 25 '12 at 21:17

score 1 · Answer 1 · answered Sep 25 '12 at 20:28

1

public void processPermutations(String s) {
  for (int i=1; i<s.length; i++) {
    String substring = s.substring(0, i);
    // Generate and process the permutations of the substring here...
  }
}

answered Sep 25 '12 at 20:28

maerics

151,642
46
269
291

That wont work, for the permutations of 123 results in 1 12 21 123 132 213 231 312 321 I need to get 13 31 32 23, ect. as well. – user1681891 Sep 25 '12 at 20:32
This will not get him all the permutations. If the string is ABC with this code he will never get AC, BC and C – Christina Sep 25 '12 at 20:32
@Christina And AA BB CC AAA also required. – Roman C Sep 25 '12 at 21:01
@Roman, you're right. I updated my answer. – Christina Sep 25 '12 at 21:11
@Christina Don't forget repetitions within permutations you didn't posted. – Roman C Sep 25 '12 at 21:20

Christina · Answer 2 · 2012-09-25T21:11:03.630

You could do something like this:

public List<String> getPermutations(String s) {
    List<String> result = new ArrayList<String>();

    if (s.length() > 1) {
        for (int i = 0; i < s.length(); i++) {
            //Create a string that has all the characters of s except the ith one
            String smallerString = s.substring(0,i) + s.substring(i + 1, s.length());
            result.addAll(getPermutations(smallerString));

            //Get permutations involving a single character appearing multiple times,
            //ie. AA, AAA, AAAA, etc.
            String repeatString = new String();
            for (int j = 1; j <= s.length(); j++) {
                repeatString = repeatString + s.charAt(i);
                result.add(repeatString);
            }
        }
    }

    //Add all the permutations using all the string's characters to the list here.
    return result;
}

Try not to think of the complexity of that however ;)

You're right, I used s.size() instead of s.length() by mistake. It's fixed now. — Christina, Sep 25 '12 at 20:38
I haven't added the actual code which will get the permutations of a string using all its characters since he already knows how to do this. This should be added in the part which says //Add all the permutations using all the string's characters to the list here. — Christina, Sep 25 '12 at 20:46

score 0 · Answer 3 · answered Sep 25 '12 at 21:05

You have to get the combinations of the string first into a descending number of buckets, then permute on each combination bucket. For example, if your string has 3 characters:

Combinations of "ABC" choose 3 = 1 Combinations of "ABC" choose 2 = 3 Combinations of "ABC" choose 1 = 3

Thus, you need to find the permutations of each of these 7 cases. In pseudocode:

int lenString = s.length
int[] all_permutations = new array
for( buckets = 1 to lenString ){
    int[] c = Combinations( s, buckets )
    int[] p = Permutations( c )
    all_permutations += p   
}

String Permutations Java

3 Answers3