Java generate all possible permutations of a String

Question

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?

I don't think you will be able to generate more strings than that per second. — Dogbert, Dec 22 '12 at 19:02
why do you need all permutations? (maybe the task can be solved without generating them all) — aviad, Dec 22 '12 at 19:04
You may experience a significant boost in performance by *not* using `String.format()` here! Use and re-use a `StringBuilder` or even an array of `char` to create the strings. — JimmyB, Dec 22 '12 at 19:04
There is a limited range up to which code optimizations will work, after that, hardware issues come in to picture like CPU speed and memory latency. — S.D., Dec 22 '12 at 19:05
@Hanno: I was using multiple character arrays where the order of the characters in the arrays was different — rwb7041, Dec 23 '12 at 04:41

score 10 · Accepted Answer · edited May 23 '17 at 12:01

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.

This approach looks promising. I was trying something similar with BigInteger, but I kept on running out of memory really quickly. I'll definitely give this a try. A quick question though: In your last code snippet, why is count = 36^10 yet output is 8 characters long? And just to make sure I understand the code in the second one, the String name is ready after each iteration of the inner for loop, correct? — rwb7041, Dec 23 '12 at 04:46
@rwb7041: `36^10` was a bug, fixed, thanks! And yes, `name` holds ready value, `00000000` during first iteration and `ZZZZZZZZ` in last. — Tomasz Nurkiewicz, Jan 07 '13 at 17:29

score 0 · Answer 2 · answered Dec 22 '12 at 19:24

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

Java generate all possible permutations of a String

2 Answers2