因为所有可能的排列组合有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://webptt.com/cn.aspx?n=bbs/Python/M.1503395888.A.4C4.html