Java 生成字符串的所有可能排列

Question

我知道这个问题已经被问过很多次了，但是我正在寻找一种非常快速的算法来生成长度为 8 的字符串的所有排列。我正在尝试生成一个长度为 8 的字符串，其中字符串中的每个字符可以是任何字符 0-9 或 a-z(总共 36 个选项)。目前，这是我必须做的代码:

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

如您所见，这段代码无论如何都不漂亮。此外，此代码每秒可以生成 28 万个字符串。我正在寻找一种比这更快的算法。

我尝试了一种递归方法，但它的运行速度似乎比这种方法慢。有什么建议吗？

Answer 1

应该更快(每秒产生超过百万个输出)，至少阅读起来肯定更愉快:

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

这利用了您的问题:

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)

可以重新表述为:

在 base-36 系统中打印从 0 到 36^8 的所有数字。

几点说明:

• 输出按定义排序，不错!

• 为了简单起见，我使用 StringUtils.leftPad()，另请参阅:How can I pad an integers with zeros on the left?

• 你要找的并不是真正的 permutation

• 利用您生成所有后续数字这一事实，您可以轻松地进一步改进此算法:

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

上面的程序，在我的电脑上，每秒生成超过 3000 万 个字符串。而且还有很大的改进空间。