CODEWITHSUNDEEP
javastringpermutation
rwb7041
rwb7041

Reputation: 145

Java generate all possible permutations of a String

I know this question has been asked many times, but I'm looking for a very fast algorithm to generate all permutations of Strings of length 8. I am trying to generate a String of length 8, where each character in the String can be any of the characters 0-9 or a-z (36 total options). Currently, this is the code I have to do it:

for(idx[2] = 0; idx[2] < ch1.length; idx[2]++)
for(idx[3] = 0; idx[3] < ch1.length; idx[3]++)
    for(idx[4] = 0; idx[4] < ch1.length; idx[4]++)
        for(idx[5] = 0; idx[5] < ch1.length; idx[5]++)
            for(idx[6] = 0; idx[6] < ch1.length; idx[6]++)
                for(idx[7] = 0; idx[7] < ch1.length; idx[7]++)
                    for(idx[8] = 0; idx[8] < ch1.length; idx[8]++)
                        for(idx[9] = 0; idx[9] < ch1.length; idx[9]++) 
                            String name = String.format("%c%c%c%c%c%c%c%c%c%c",ch1[idx[0]],ch2[idx[1]],ch3[idx[2]],ch4[idx[3]],ch5[idx[4]],ch6[idx[5]],ch7[idx[6]],ch8[idx[7]],ch9[idx[8]],ch10[idx[9]]);

As you can see, this code is not pretty by any means. Also, this code can generate 280 thousand Strings per second. I'm looking for an algorithm to do it even faster than that.

I've tried a recursive approach, but that seems to run slower than this approach does. Suggestions?

Upvotes: 3

Views: 2725

Answers (2)

Tomasz Nurkiewicz
Tomasz Nurkiewicz

Reputation: 340708

Should be faster (generates way above million outputs per second), and at least it's definitely more pleasant to read:

final long count = 36L * 36L * 36L * 36L * 36L * 36L * 36L * 36L;

for (long i = 0; i < count; ++i) {
    String name = StringUtils.leftPad(Long.toString(i, 36), 8, '0');
}

This exploits the fact that your problem:

generate a String of length 8, where each character in the String can be any of the characters 0-9 or a-z (36 total options)

Can be reformulated to:

Print all numbers from 0 until 36^8 in base-36 system.

Few notes:

  • output is sorted by definition, nice!

  • I'm using StringUtils.leftPad() for simplicity, see also: How can I pad an integers with zeros on the left?

  • what you are looking for is not really a permutation

  • by exploiting the fact that you generate all subsequent numbers you can easily improve this algorithm even further:

    final int MAX = 36;
final long count = 1L * MAX * MAX * MAX * MAX * MAX * MAX * MAX * MAX * MAX * MAX;

final char[] alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
final int[] digits = new int[8];
final char[] output = "00000000".toCharArray();

for (long i = 0; i < count; ++i) {
    final String name = String.valueOf(output);

    // "increment"
    for (int d = 7; d >= 0; --d) {
        digits[d] = (digits[d] + 1) % MAX;
        output[d] = alphabet[digits[d]];
        if (digits[d] > 0) {
            break;
        }
    }

}

Program above, on my computer, generate more than 30 million strings per second. And there's still much room for improvement.

Upvotes: 10

JimmyB
JimmyB

Reputation: 12610

This code may look a little prettier - or at least more complex ;)

boolean incrementIndex( int[] idx, final int maxValue ) {
  int i = 0;
  int currIndexValue;
  do {
    currIndexValue = idx[i];
    currIndexValue++;
    if ( currIndexValue > maxValue ) {
      currIndexValue = 0;
    }
    idx[i] = currIndexValue;
    i++;
  } while ( currIndexValue == 0 && i < idx.length );

  return i < idx.length;
}



do {
  // create String from idx[0]...idx[8]
} while ( incrementIndex(idx, 35) );

Upvotes: 0

Related Questions