作者kaneson (Lance)
看板Programming
標題Re: [討論] 排列組合的演算法解題
時間Sun Sep 6 11:12:55 2020
為了打發時間想了一個遞迴解
# call poss(7, 4, 0) in main()
def poss(field, pick, cur_max):
if field < pick:
return 0
if pick == 0:
return cur_max ** field
if field == 0:
return 0
_sum = 0
i = cur_max if cur_max > 0 else 1
for n in range(i, 10):
_sum += poss(field-1, pick-1, n)
_sum += i * poss(field-1, pick, cur_max)
return _sum
第一個參數是剩餘欄位數
第二個參數還有幾個欄位要滿足條件
第三個就是當前最大值
其中如果滿足的位數已經取完且還有剩餘位，
例如 1234*** 剩下三位各可以取0~3，
可以直接算所以就列入base case
general case 的話這裡不好說明，
自己在紙筆上展開可能比較好理解，
原則上就是分為目前最高位是否要取大於等於目前最大值。
例如 poss(3, 1, 5)
意思是目前剩3位,還有1位要滿足不小於5,
可以展開成目前最大位要滿足, 有5~9,
所以後面就是poss(2, 0, 5) ~ poss(2, 0, 9)
還有目前最大位不要滿足, 有0~4,
所以後面就是 5組 (0~4) poss(2, 1, 5)
而當前最大值是0的話比較特別，
想了很久一開始也完全想不到如何把它湊進遞迴式裡
我自己的電腦可以跑在0.008秒內
不過我如果是在短時間限制的面試裡大概也只寫得出brute force XD
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.154.236 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Programming/M.1599361977.A.673.html
※ 編輯: kaneson (114.32.154.236 臺灣), 09/06/2020 11:14:12
※ 編輯: kaneson (114.32.154.236 臺灣), 09/06/2020 11:24:34
※ 編輯: kaneson (114.32.154.236 臺灣), 09/06/2020 11:25:45
※ 編輯: kaneson (114.32.154.236 臺灣), 09/06/2020 11:29:20