Re: [問題] 樣本排列組合的問題

[poototo (poototo)]

若只是在需要時，能隨機提供其中一種排列可能，就O(n)而已
這樣教授可以接受嗎?

底下是leetcode的題目
---------------------------------------
import math
#
def getPermutation(n, k):
    raw = [i for i in range(1, n + 1)]
    ans = []
    #
    batch = 1
    for i in range(1, n + 1):
        batch *= i
    #
    for i in range(1, n + 1):
        batch /= (n - (i - 1))
        pos = math.ceil(k / batch) - 1
        ans.append(raw[pos])
        del raw[pos]
        #
        k -= batch * (k // batch)

    #
    print(ans)


#
getPermutation(21, 16673)





※ 引述《GoGoApo (Apo)》之銘言：
: 各位前輩好
: 小弟我目前手上有21個樣點資料，需要做不同的排列組合來嘗試他最終結果，這樣就有21
: ！種可能。
: 目前是以itertools.pertutations來做，可是光是產生出所有組合電腦就不太能負荷
: 想請問有沒有其他方法可以使用？
: 或是該怎麼寫才能讓他不會當機
: 目前是Jupyter notebook只要再開同個檔案他就會當機
: 請各位前輩指教了

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.43.58 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1579371201.A.DC3.html
→ ddavid: 原Po問題也沒講清楚，不過怎麼看也不可能是這樣
→ GoGoApo: 謝謝前輩還願意回答我的問題，但教授不是要求這樣。
→ GoGoApo: 回D大：目前我遇到的困難是有21個樣點要分成五組，前四
→ GoGoApo: 組各四個樣點，第五組五個樣點，每一組代表一年的調查資
→ GoGoApo: 料，然後每一年都要進行一次預測。教授想知道各種排列組
→ GoGoApo: 合對預測的影響有多大，所以一開始要我不管排序直接用21
→ GoGoApo: ！下去看所有組合，後來討論過後就變成考慮排序，但還是
→ GoGoApo: 有約一兆多種組合，目前是改用itertools.combinations來
→ GoGoApo: 讓他產生每五年的為一期的樣點序列這樣子。
推 ddavid: 如果只是想知道不同排列組合對於預測的影響，則可以用隨機
→ ddavid: 的方式在時間容許範圍內跑足夠多組合，觀察其變化程度就可
→ ddavid: 做一個基本的估計了，沒有必要非得把每一組都跑完
→ ddavid: 你只要跟你的教授說，就算我現在跑完了所有的排列組合，那
→ ddavid: 萬一我又多了一組資料，是否又得全部重跑所有排列組合得出
→ ddavid: 最佳的那一組？這樣只會導致方法完全沒有泛用與實用性，每
→ ddavid: 次碰到新資料就要全部重跑巨量次數的方法絕對不會是理想的
→ ddavid: 方法
推 ddavid: 而且嚴格說來這要求看起來我也沒有覺得很合理，如果樣本點
→ ddavid: 原本就具有時間順序，怎麼可以隨便亂搬動到哪一年去然後才
→ ddavid: 來看怎麼湊結果比較好
→ ddavid: 這就好像我在湊一組讓我方法最好的資料搭配一樣，其實已經
→ ddavid: 近似在造假資料了
→ ddavid: 當然這是只從你這邊的簡單說明，以我的背景知識的感想而已
→ ddavid: ，有可能實際上不是這樣，只是我對問題還沒真正清楚