[筆記][想法]在排列組合中找出最好的結果

[筆記][想法]在排列組合中找出最好的結果

寒假時和學長討論到,要寫個程式找出排列組合中最好的結果 (aka用程式排比賽裁判),雖然大概要7月才能動工,不過還是先把想法記錄下來避免到時候忘記。總覺得好像常常忘記靈光一現的想法過沒多久就會忘記了,果然好記性不如爛筆頭XD

基本構思

  • 用正負分數表示對組合的偏好,希望能輸出分數最高的組合
  • 篩選組合分2種方式
    • 裁判對學校
    • 裁判對裁判
  • 分別用清單儲存 賽程、裁判、篩選規則,以方便調用

想法一、算出所有的結果

  一開始的想法,不過實際上不太可行。雖然python有函數可以產生所有組合的List,不過在測試時產生12!的所有組合就會占用幾乎大量記憶體(我的電腦配置是16G),而且需要大量的讀取時間才能印出結果,更會有許多不必要的計算(之後在想法三說明),所以拋棄了這個想法。這邊紀錄一下一開始所使用的程式碼。

  因為直接印出會爆炸,所以失敗後想到了分批產生的方法,並且只保留分數最高的100組數據,避免佔據過多記憶體空間。說到這邊就想到明明就有sorted(List),老師還是用一個一個去比對大小的方式取出List中前n高的數據,那時候還不明所以,現在才想到,大概是當遇到這種List過於龐大的時候,也只能用這樣的方式處理。

  因為P(15,15)=P(15,3)xP(12,3)xP(9,3)xP(6,3)xP(3,3),所以可以先處理P(15,3),並產生記錄檔用的folder,之後先清除資料,再依序從每個folder下做P(12,3),以此類推。做到最後一層時再與目標清單(前n高的分數)比對,若高於清單內的分數就儲存在清單,反之就拋棄數據,清單內前只留n高的數據,做完之後return回上層。

  但就是更改過後的方法,也頂多能解決因為占用過多記憶體導致崩潰的問題,所需要的計算讀取時間以及不必要的計算仍然過多,所以還是拋棄了XD

想法二、抽樣法—在隨機n組中取分數最高的組合

  其實這是原本的想法,不過被學長說會不太嚴謹所以也放棄了XD 做法是做n個迴圈,在每個迴圈中直接random打亂排列順序,再計算分數,最後再從這n組裡面依照分數排序。

  正當我正為了龐大的計算量而一籌莫展的時候, 那一天,我有了新的想法

想法三、只計算會影響分數的組合

  因為我們的目標是取出分數最高的組合,所以其實可以不用計算不會影響分數的組合,也就是只要依據篩選列表中的組合做計算就好。

—未完待續—

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *