→ ptt0720: 感謝您，研究中 08/23 03:02
因為所有可能的排列組合有N!種，就算算到一半停下來，
時間複雜度也是O(N!)，當N>15的時候一般電腦可能就跑不出來了，
故不太可能窮舉。
我們回頭來觀察s='abc'的排列組合
abc
acb
bac
bca
cab
cba
後發現現兩件事情：
1. 每個字串的首字元排序有一定的規則，
每個字元都剛好在字串首出現了(N-1)!次，而且是排列有序的。
所以我們想知道，排第ith(從0開始)的字串首字元為何，
只要找出rank = ith // (N-1)!，則s[rank]就是該字串的首字元。
ex: 3th的字串'bca'，rank = 3 // (3-1)! = 1, s[1]即是該字串的首字元'b'。
2. 找完首字元後，我們只要繼續找出去掉首字元的子字串首字元為何，
就能一路遞迴下去找完整個字串。
一樣用3th的字串'bca'為例，
...
b ac 0th
b ca 1th
...
他是在以b為首的字串中排1th，也就是剛剛算rank時的餘數
3 / (3-1)! = 1 ... 1
因為sub_s = 'ac'，故next_rank = 1 // (2-1)! = 1, sub[next_rank]='c'
有了上述兩點觀察，我們就可以用遞迴的方式找到排行ith的字串，
要找到N!//2th的字串也不是問題。
這邊是程式碼：
https://gist.github.com/Hutdris/bd377d183e8e3983e4549a9fa4304115
時間複雜度是O(N), 但因為N!可能會超過INT_MAX，怕整數運算出錯所以設了一個
MAX_N=20。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.73.123
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1503395888.A.4C4.html