作者uranusjr (←這人是超級笨蛋)
看板Python
標題Re: [問題] 排列組合只取一半
時間Tue Aug 22 03:07:21 2017
※ 引述《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
--
1F：→ GNUGCC:void main(void) 的寫法是可行的唷^^08/10 00:59
2F：→ GNUGCC:雖然這個寫法較傳統,但是語法與文法都正確哦^^08/10 02:16
3F：→ GNUGCC:目前我使用的 Visual C++ 都接受 void main(void) 與 08/10 20:18
4F：→ GNUGCC:int main(void),各位可以把 C++ 專案改成原生 C++ 類型來 08/10 20:19
5F：→ GNUGCC:用 void main(void) 來寫發現也可通過編譯. 08/10 20:21
6F：→ GNUGCC:這個就是 Visual C++ 的彈性.08/11 20:23
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.161.19.12
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1503342443.A.93D.html
7F：→ bibo9901: 這樣還是 O(n lgn) 08/22 10:28
8F：→ bibo9901: 概念是遞迴 但實際上可以用迴圈做 08/22 10:28