Re: [討論] 排列組合的演算法解題
首先畫個圖:
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
09/01 15:05, 3F
→
09/01 15:05,
4年前
, 4F
09/01 15:05, 4F
→
09/01 15:06,
4年前
, 5F
09/01 15:06, 5F
推
09/01 19:01,
4年前
, 6F
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
討論串 (同標題文章)
完整討論串 (本文為第 3 之 7 篇):
討論
1
3