作者ptt0720 (濕濕)
看板Python
標題Re: [問題] 排列組合只取一半
時間Tue Aug 22 05:44:54 2017
※ 引述《uranusjr (←這人是超級笨蛋)》之銘言：
: 推文有提到遞迴方法
: 不過 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
感謝您的解釋 算是稍微了解迭代器(iterator)的運作方式了
我也把code改成這樣
http://i.imgur.com/40wI9d8.png
但送出之後 系統還是覺得我的運算時間太長了
我也直接把題目po出來 希望能夠拋磚引玉囉
https://www.codewars.com/kata/simple-fun-number-159-middle-permutation/train/python
--
生如夏花之絢爛，
死如秋葉之靜美。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.67.167.138
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1503351900.A.E37.html
1F：→ ptt0720: 連結被斷行了 請大大們注意一下囉 08/22 05:46
2F：推 hutdris: n個字母的排列組合有n!種，就算只生成一半依然要O(n!)。 08/22 15:03
3F：→ hutdris: 這題應該是要你直接找字串排序後的特性用遞迴去解。 08/22 15:03