Java生成String的所有可能排列

Question

我知道这个问题已被多次询问,但我正在寻找一种非常快速的算法来生成长度为8的字符串的所有排列.我试图生成一个长度为8的字符串,其中字符串中的每个字符都可以是任意字符串字符0-9或az(总共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]]);

正如您所看到的,这段代码无论如何都不是很漂亮.此外,此代码每秒可生成280,000个字符串.我正在寻找一种比这更快的算法.

我尝试了一种递归方法,但这似乎比这种方法运行得慢.建议？

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

这利用了你的问题:

生成一个长度为8的String,其中String中的每个字符可以是0-9或az中的任意一个字符(总共36个选项)

可以重新表述为:

打印所有数字0,直到36^8在基地-36系统.

几点说明:

• 输出按定义排序,很好!

• 我是StringUtils.leftPad()为了简单而使用,另请参阅:如何在左侧用零填充整数？

• 你在寻找什么并不是一种排列

• 通过利用您生成所有后续数字的事实,您可以进一步轻松改进此算法:

  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万个字符串.而且仍有很大的改进空间.