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

Question

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

3

我知道这个问题已经被问了很多次，但我正在寻找一种非常快速的算法来生成长度为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万个字符串。我正在寻找一种比这更快的算法。

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

- rwb7041

我认为你无法每秒生成更多的字符串。 - Dogbert

为什么每秒280,000个字符串还不够快？ - Matt Ball

为什么需要所有排列？（也许可以在不生成它们的情况下解决任务） - aviad

2

在这里不要使用 String.format() ，使用和重用 StringBuilder 或者甚至是 char 数组可以显著提高性能。 - JimmyB

@Hanno：我使用了多个字符数组，其中每个数组中字符的顺序都不同。 - rwb7041

显示剩余3条评论

2个回答

0

这段代码看起来可能会更漂亮一些 - 或者至少更复杂一些 ;)

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

- JimmyB

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tomasz Nurkiewicz · Accepted Answer

应该更快（每秒生成的输出远超过百万），而且至少阅读起来肯定更愉快：

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的字符串，其中字符串中的每个字符可以是0-9或a-z的任意一种字符（共36种选项）

可以重新表述为：

在基数为36的系统中打印从0到36^8的所有数字

一些注意事项：

输出已按定义排序，很好！
我使用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万个字符串。而且还有很大的优化空间。