2

この質問が何度も聞かれることは知っていますが、長さ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]]);

ご覧のとおり、このコードは決してきれいではありません。また、このコードは1秒あたり28万の文字列を生成できます。それよりもさらに速く実行するアルゴリズムを探しています。

再帰的なアプローチを試しましたが、このアプローチよりも実行が遅いようです。提案？

4

2 に答える 2

10

より高速である必要があり（1秒あたり100万をはるかに超える出力を生成します）、少なくとも読む方が間違いなく快適です。

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またはazの任意の文字にすることができます（合計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;
        }
    }

}

上記のプログラムは、私のコンピューターで、毎秒3,000万を超える文字列を生成します。そして、まだまだ改善の余地があります。

于 2012-12-22T19:10:05.317 に答える
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) );
于 2012-12-22T19:24:54.507 に答える