※ 引述《ptt0720 (濕濕)》之銘言：
: 最近寫題目寫到一題
: http://i.imgur.com/vYeB7nL.png
: 要先把字串依照a b c順序排列好
: 之後進行排列組合
: 然後印出最中間的那一筆
: 我用的方法是itertools的module
: 但是在server進行運算的時候 系統說我超過時間了
: 限制時間是12000ms
: 我的code
: http://i.imgur.com/YvcrD7b.png
: 我在想應該是產生全部排列組合太沒有效率了
: 但是又不知道如何生成一半組合就好
推文有提到遞迴方法
不過 CPython 對遞迴支援那麼差我猜一定爆炸慢, 就不管了
解釋一下用 next 的做法
itertools.permutations 是回傳一個 permutation iterator
而 Python 內建的 next() 函式可以得到一個 iterator 的「下一個」結果
當你對 iterator 做 for 運算時, Python 其實也就是不斷取得下一項
所以像下面的程式
for i in iter('abc'):
print(i)
可以大概翻譯成
it = iter('abc')
try:
while True:
i = next(it)
print(i)
except StopIteration: # 代表沒有下一個了
pass
那所以你就可以這樣找到中間項, 而避免執行整個 iterator
perm_it = itertools.permutations(input_value)
for _ in range(中間項的位置):
next(perm_it)
print('item in the middle:', next(perm_it))
好那下一個問題就是要怎麼知道中間項的位置
幸好 permutation 的數量有公式解
Python 沒有 product 函式 (如果有 numpy 就簡單了)
所以你得自己算
permutation_count = 1
for i in range(1, len(input_value) + 1):
permutation_count *= i
中間項的位置就是 permutation_count // 2 - 1

void main(void) 的寫法是可行的唷^^雖然這個寫法較傳統,但是語法與文法都正確哦^^目前我使用的 Visual C++ 都接受 void main(void) 與int main(void),各位可以把 C++ 專案改成原生 C++ 類型來用 void main(void) 來寫發現也可通過編譯.這個就是 Visual C++ 的彈性.

這樣還是 O(n lgn)概念是遞迴 但實際上可以用迴圈做