0

順列メソッドがあります

public void permute(String str) {
    permute(str.toCharArray(), 0, str.length() - 1);
}

private void permute(char[] str, int low, int high) {
    if (low == high) {
        writeIntoSet(new String(str, 0, length));
    } else {
        for (int i = low; i <= high; i++) {
            char[] x = charArrayWithSwappedChars(str, low, i);
            permute(x, low + 1, high);
        }
    }
}

private char[] charArrayWithSwappedChars(char[] str, int a, int b) {
    char[] array = str.clone();
    char c = array[a];
    array[a] = array[b];
    array[b] = c;
    return array;
}

しかし、このメソッドに 10 文字の長さの文字列を入れると、10 になります。組み合わせて、とても時間がかかります。それをより速くする方法はありますか？

編集

10文字から順列を作る必要がありますが、その後、これらの「単語」を辞書で検索します。たとえば、CxRjAkiSvH があり、CAR、CARS、CRASH などの単語が必要です。パフォーマンス オプションはありますか?

4

2 に答える 2

1

使用しているアルゴリズムよりもわずかに効率的な順列を生成するための既存のアルゴリズムがあるため、それらの 1 つを参照してください。過去に Johnson-Trotter アルゴリズムを使用したことがあります。これは、毎回次の順列を取得するための最小限の変更を可能にすることで、わずかに高速化されます。どのような制約の中で作業する必要があるかはわかりませんが、Java を使用する必要がない場合は、使用しない方がよいかもしれません。これは単に最速ではありません。特に、アルゴリズムが再帰を使用している場合。他の誰かが示唆しているように、このアルゴリズムに固執している場合は、再帰的なアプローチから離れて、ループを使用してみるのが最善かもしれません。

于 2012-06-09T16:59:20.073 に答える