更快串排列

我有置換方法更快串排列

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等字樣。是否有任何性能選項？

來源

2012-06-09 medy75

使用循環代替遞歸 – Jeffrey

如果字符串是10個字母，您需要多少個排列？ – esej

而不是構建一個大集合，您可以使用偵聽器接口來處理每個結果。 –

現在有一些生成排列的算法可能比您使用的算法效率稍高，因此您可以查看one of those。過去我使用Johnson-Trotter算法，通過儘可能少地改變每次獲得下一個排列的方式來加快速度。我不知道你需要在哪些內部工作，但如果你不需要使用Java，最好不要這樣做。這根本不會是最快的。特別是如果你的算法使用遞歸。正如其他人所建議的那樣，如果您堅持使用這種算法，您可能最好放棄遞歸方法並嘗試使用循環。

來源

2012-06-09 16:59:20 nbrooks

它必須是java，因爲我需要在Android應用程序中使用它:)它在PC上速度很快，但在手機上不是。所以，我會嘗試循環。 – medy75

對於10個字符的字符串，有10個字符！排列，沒有兩種方法。您可以通過附加StringBuffer s或手動使用char[]稍微提高速度。

來源

2012-06-09 16:44:26 Kevin

回答

相關問題