Re: [討論] 排列組合的演算法解題

看板Programming作者 (謊言接線生)時間4年前 (2020/09/01 13:11), 4年前編輯推噓3(305)
留言8則, 2人參與, 4年前最新討論串3/7 (看更多)
首先畫個圖: 9 8 7 6 5 4 3 2 1 1234567 位數 假設數值為2545397。 9 x 8 7 x 6 5 x x 4 x 3 x 2x 1 1234567 很容易可以看到,重要的是建立四個遞增點,剩下的點只要在前一個遞增點以下 就不會影響結果: 9 x 8 - 7 - 6 - 5 x x - 4 - - - 3 - - - 2x - - - 1 - - - 1234567 那麼四個遞增點怎麼建立呢?四層迴圈硬跑基本上寫得正確就不會跑出不可能的 狀態,也就是後數比前數大或相等即可(以Python為例,注意range(a, b)表示包含a 到(b-1)): sum = 0 n_list = [0] * 4 for n_list[0] in range(0, 10): for n_list[1] in range(n_list[0], 10): for n_list[2] in range(n_list[1], 10): for n_list[3] in range(n_list[2], 10): sum += poss_num(n_list) 每建立一套遞增點,例如2559,那麼我們就要插入剩下三個數並確保三個數不會 影響遞增點數量。 首先觀察2前面不能插值,因為2前面<= 2會使遞增點多一,> 2會使2不再是遞增 點。 再來,如果我們要插在2跟5之間,合法值有幾個?答案是0、1,也就是< 2的兩 個數。同理,插在5跟5之間只要看前面的5而可以接受0~4,5跟9之間也是看5而同樣 是0~4,9之後則是0~8。也就是說,很巧地,你要插一個值到x這個值後面,就有x這 麼多種不重複的可能性。 我們驗證一下極端值0是不是也符合?0369為例,0後面可以插值而不影響遞增數 量或位置嗎?看來是不行的,插個0或以上就變成遞增五個數了,所以0後面插值的可 能性確實是0種。 那麼同樣2559為例,如果我們要插2個值在2後面,1個在9後面,有幾種可能? 2005590 2005591 2005592 . . 2005598 2015590 . . 2115598 接在2後面的值有2種可能,9後面就有9種可能,所以是2*2*9 = 36。也就是說, 我們甚至都不用列出來,直接可以簡單乘法就算出這邊的可能性。 那麼同樣跑完全沒有多餘的迴圈來決定三個數「依序」插在哪裡,就可以個別用 上述公式解算出各種插入位置的可能性。第一個數可以有四個位置選擇(四個遞增點 之後),第二個數必須在第一個數同樣或更後面的位置,以此類推。最後就可以加總 : def poss_num(n_list): sum = 0 pos_list = [0] * 3 for pos_list[0] in range(0, 4): for pos_list[1] in range(pos_list[0], 4): for pos_list[2] in range(pos_list[1], 4): sum += ( n_list[pos_list[0]] * n_list[pos_list[1]] * n_list[pos_list[2]] ) return sum 總結一下,關鍵就在於兩個點: 1. 選取數字時的迴圈怎麼樣徹底避開不可能狀況 -> 兩者都是遞增 2. 遞增四個數字以及插入位置確定後,如何避免一一窮舉 -> 注意到內層有公式解 注意Python完整Code要把poss_num()的定義搬到主迴圈前面去。執行時間基本上 按下去就出來了。 有心的話可以將兩個多層迴圈都改寫為stack,這樣你就可以處理此問題的通解 :任意位數,任意遞增長度。 -- 「傳說的最後,魔王總是被勇者封印。但勇者會逝去、封印會衰弱,魔王卻永遠 不滅。傳說呢?傳說持續著。只是,變質了。所以對於傳說而言,只有反覆無常的自 己是主角,而魔王只是配角。勇者?勇者不過是消耗品罷了,封印則什麼也不是。妳 好不容易有機會當上配角,怎麼走回頭路想成為消耗品?妳早晚會什麼也不是的。」 --星.幻.夢的傳說 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.17.60 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1598937076.A.A19.html ※ 編輯: ddavid (114.32.17.60 臺灣), 09/01/2020 13:14:25

09/01 14:46, 4年前 , 1F
試了一下,時間差不多(有點出乎意料)
09/01 14:46, 1F
還好,你的改良版cut方式夠好,該砍的都有砍掉的話,大概就只多一些量不大 的邏輯判斷成本吧。

09/01 14:47, 4年前 , 2F
但你的方法空間應該好不少
09/01 14:47, 2F
※ 編輯: ddavid (114.32.17.60 臺灣), 09/01/2020 14:53:04

09/01 15:05, 4年前 , 3F
檢查了一下,我的查表中只有165個項目
09/01 15:05, 3F

09/01 15:05, 4年前 , 4F
而且只被查了175次
09/01 15:05, 4F

09/01 15:06, 4年前 , 5F
效率出乎意料的好
09/01 15:06, 5F

09/01 19:01, 4年前 , 6F
感謝s大跟d大兩位的分享。線上測驗的
09/01 19:01, 6F

09/01 19:01, 4年前 , 7F
解題時間大概十分鐘,加上緊張越想越
09/01 19:01, 7F

09/01 19:01, 4年前 , 8F
打結。從兩位的解題思維學到很多!
09/01 19:01, 8F
※ 編輯: ddavid (1.164.183.14 臺灣), 11/21/2020 02:01:20
文章代碼(AID): #1VJTVqeP (Programming)
討論串 (同標題文章)
文章代碼(AID): #1VJTVqeP (Programming)