Re: [問題] 排列組合只取一半

作者: ptt0720 (濕濕)   2017-08-22 05:44:54
※ 引述《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改成這樣


但送出之後 系統還是覺得我的運算時間太長了
我也直接把題目po出來 希望能夠拋磚引玉囉
https://www.codewars.com/kata/simple-fun-number-159-middle-permutation/train/python
作者: ptt0720 (濕濕)   2017-08-22 05:46:00
連結被斷行了 請大大們注意一下囉
作者: hutdris   2017-08-22 15:03:00
n個字母的排列組合有n!種,就算只生成一半依然要O(n!)。這題應該是要你直接找字串排序後的特性用遞迴去解。

Links booklink

Contact Us: admin [ a t ] ucptt.com