查找Java中排列的最有效方法[具有較低的漸近複雜度]

我的目標是查找字符串的所有排列組合。經過一些快速搜索，我發現了一個很好的方法來查找字符串的所有排列。即查找Java中排列的最有效方法[具有較低的漸近複雜度]

private static void permutation(String prefix, String str) 
    { 
     int n = str.length(); 
     if (n == 0) 
      System.out.println(prefix); 
     else 
     { 
      for (int i = 0; i < n; i++) 
       permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)); 
     } 
    }

我相信這種方法的複雜性是O（n！）（糾正我，如果我錯了）。而我的問題是：我可以調整它來改善效率嗎？還是有更好的選擇來產生所有的排列？

來源

2016-03-07 OBX

可能重複的[更快的字符串排列]（http://stackoverflow.com/questions/10962682/faster-string-permutation） – Whymarrh

除非有重複的字符，它將是O（n！） –

@dr_debug你是什麼通過刪除遞歸來達到性能的目的？你是否建議使用循環而不是遞歸？ – OBX

它看起來像你使用這樣的回答：

Generating all permutations of a given string

對這個問題的意見是相當有價值的信息。在字符串操作上你有很多效率低下的問題，它會打印重複的文件，它不會記錄重複的字符，還有一些其他的記錄。

我會仔細查看這些內容，實施建議的更改，然後比較一下，看看您的運行時間改進是多少。基本上我相信你是以n爲界的！而且你可以做的最多的是內存/數據結構的調整，以避免空間/時間複雜性爆炸，因爲這裏使用的結構應用效率低下。

來源

2016-03-07 18:18:15

查找Java中排列的最有效方法[具有較低的漸近複雜度]

回答

相關問題