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

看板Programming作者ddavid (謊言接線生)時間4年前 (2020/09/01 13:11)推噓3(3推 0噓 5→)

留言8則, 2人參與討論串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