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

[uranusjr (←這人是超級笨蛋)]

※ 引述《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

--
→ GNUGCC:void main(void) 的寫法是可行的唷^^
→ GNUGCC:雖然這個寫法較傳統,但是語法與文法都正確哦^^
→ GNUGCC:目前我使用的 Visual C++ 都接受 void main(void) 與
→ GNUGCC:int main(void),各位可以把 C++ 專案改成原生 C++ 類型來
→ GNUGCC:用 void main(void) 來寫發現也可通過編譯.
→ GNUGCC:這個就是 Visual C++ 的彈性.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.161.19.12
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1503342443.A.93D.html
→ bibo9901: 這樣還是 O(n lgn)
→ bibo9901: 概念是遞迴 但實際上可以用迴圈做