3

Possible Duplicate:
Generating all permutations of a given string

Given a length n=4, and a set of characters -> {'a', 'b'}, how to write some java codes to produce all the possible string with that length n containing the characters in the set?

For the example above, the result should have 2^4=16 strings, which is:

aaaa
aaab
aabb
abbb
baaa
baab
babb
bbbb
bbaa
bbab
bbba
abaa
abab
abba
baba
aaba

here is my code snippet:

public void process(String result, String string)
{
    if(string.length() == 0)
    {
        System.out.println(result);
    }else{
        for(int i = 0; i < string.length(); i++)
        {
            String newResult = new String(result+string.charAt(i));
            String newString = new String(string.substring(0,i) + string.substring(i+1, string.length()));
            process(newResult, newString);
        }
    }
}

That seems like only doing permutation, instead of what I want....... Thank you in advance :)

Community
  • 1
  • 1
Evan_HZY
  • 984
  • 5
  • 17
  • 34
  • http://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string – Peter Svensson Sep 05 '12 at 20:00
  • @Matteo I have tried to use similar code from the string permutation, but I failed to get the correct result... – Evan_HZY Sep 05 '12 at 20:01
  • Go to the theory first: http://en.wikipedia.org/wiki/Permutations – davidmontoyago Sep 05 '12 at 20:01
  • 1
    user1182328 please show us your code and tell us what was the error you detected, so we can help you. – SJuan76 Sep 05 '12 at 20:02
  • @BlackVegetable it is not a homework – Evan_HZY Sep 05 '12 at 20:02
  • 2
    By the way these are not permutations, I think they are variations with repetition. Permutations is when you have several distint elements and you have to order them, without repeating any (at most you can have several elements that are the same) – SJuan76 Sep 05 '12 at 20:04
  • @SJuan76 Correct, it's [combinations](http://en.wikipedia.org/wiki/Combination) with repetition. – Brian Sep 05 '12 at 20:12

3 Answers3

7

Think of it in the same way you would counting. You're technically "counting" from aaaa to bbbb, like binary.

aaaa -> 0000
aaab -> 0001
aaba -> 0010
aabb -> 0011
...
bbbb -> 1111

Without seeing what you've tried, I can't help you more than that, but essentially you need to enumerate all the "numbers" between your "lowest" element and your "highest" element by counting up through them.

For higher element counts, just treat your counting as counting in a higher base. For eight elements, Set = {a, b, c, d, e, f, g, h}, you would be counting up in what's essentially octal:

aaaa -> 0000
aaab -> 0001
...
aaah -> 0007
aaba -> 0010
...
hhhh -> 7777

It's the same way you enumerate all the combinations of 0-9 with a length of 4, by counting from 0000 to 9999.

Edit:

Thank you for posting your code. You're correct, you're doing permutations. A better way would be to use a multi-combination (combination with repeated elements in the ordererd combination set) algorithm like the one discussed here.

Brian
  • 17,079
  • 6
  • 43
  • 66
  • 1
    I'm not sure this binary visualisation helps in a question that could include more than two characters in the allowed set. – Duncan Jones Sep 05 '12 at 20:04
  • 1
    @DuncanJones anyway it is the same, if you have n different elements you are writting "numbers" in base-n. – SJuan76 Sep 05 '12 at 20:05
  • @DuncanJones Sure it does, just extend the concept to a higher base, such as base-8 for 8 elements. – Brian Sep 05 '12 at 20:06
  • @DuncanJones I updated the answer to clarify higher bases – Brian Sep 05 '12 at 20:11
  • @Brian My comment was mostly around whether this visualisation (regardless of base) helps in solving the issue. But I suppose that was presumptuous of me as not everyone's minds work the same! And I think the +1 votes show that I'm in the minority :-) – Duncan Jones Sep 05 '12 at 20:21
  • @DuncanJones Of course, all is well :) Combinatorics made more sense to my class and me when our teacher explained it using number systems, since we all understood how to count. Teaching it as I learn it. Though it probably was a good idea to include another base to clarify anyway, so thank you. – Brian Sep 05 '12 at 20:24
0

This may be error prone, as I haven't tested it, but it should work. Even if it doesn't, it should be extremely close to what you are looking for. Note that the first for loops populate the resultList instead of setting values, as there will be nothing to append to.

Let me know if there is an issue and I will correct it.

ArrayList<String> results = new ArrayList<String>();
ArrayList<String> components = new ArrayList<String>(){"a","b","c"};
int n = 4;

int size = components.size();
for ( int j = 0; j < size; j++ )
{
  // start with size^(n-1) copies of each letter. 
  for ( int i = 0; i < Math.pow( size, n-1); i++ )
  {
    results.add( components.get( j ) );
  }
}

// At this point you have each letter in there once...

for( int depth = 1; depth < n; depth++ )
{
  for( int j = 0; j < size; j++ )
  {
    String toAppend = components.get( j );
    for( int i = j; i < results.size(); i += size )
    {
      String current = results.get( i );
      current += toAppend;
      results.set( i, current );
    }
  }
}
BlackVegetable
  • 12,594
  • 8
  • 50
  • 82
0

You've got an answer, but I feel that you need some more help:

if(string.length() == 0)
{
System.out.println(result);
}

Why would you print an empty string? It will print nothing at all. You may want to print a message and exit from your function.

Silviu Burcea
  • 5,103
  • 1
  • 29
  • 43
  • He checks if the `string` length is `0` then prints `result`, not `string`, so this is incorrect. – Brian Feb 11 '13 at 17:50