母函數入門

01-25

母函數入門

問題引入

假設我們當前有質量分別為 1g, 2g, 3g, 4g 的砝碼各一個, 我們可以構造出多少種質量為7g的砝碼方案?

基礎解法

顯然, 想要指定重量的砝碼序列的構造, 對於每一個砝碼, 我們都有使用或者不使用兩種選擇. 如果我們對每個砝碼進行枚舉的話, 則共需要枚舉 $2^4$ 種選擇, 即這種解法的時間複雜度為 $O(2^n)$ .

代數解法

我們定義變數 x 代表砝碼, x 的次冪代表砝碼的質量. 例如x4 就代表當前砝碼的質量為 4g. 那麼由選擇或者不選擇當前砝碼, 我們可以將其寫為表達式 : $(1 * x^0 + 1 * x^4)$ , $x^0$ 代表我們不選擇當前砝碼進行構造, $x^4$ 代表我們選擇當前砝碼進行構造.
那麼我們就可以將對砝碼的序列構造成一序列表達式的乘積, 即 $(1+x)(1+x^2)(1+x^3)(1+x^4)$
我們展開這個表達式, 可以得到 $1 + x + x^2 + 2x^3+ 2x^4+ 2x^5+ 2x^6+ 2x^7+ x^8+ x^9 + x^{10}$
由我們的定義可知, 冪函數對應的係數即為構造某個砝碼重量的方案數.例如 x7 的係數為 2, 那麼我們有兩種方案, 即 7 = 1 + 2 + 3 = 3 + 4

母函數定義

將一個離散序列對一個冪函數序列對應起來, 構造一個新的離散數列.
即給定離散序列 $a_0,a_1,dots,a_n$ 和冪函數序列 $x_0, x_1, dots,x_n$ , 我們構造出一個函數: $G(n) = a_0 x_0 + dots + a_n x_n = sum_i {a_i x^i}$
我們稱函數G(x) 為序列 $a_0,a_1, dots, a_n$ 的母函數

聯繫

那麼母函數與我們的方法有什麼聯繫呢? 我們來看一下一系列的一元線性函數的相乘結果 :
$egin{array}{l|r} (1+a_1x)(1+a_2x)dots(1+a_nx) \ = 1 + (a_1+a_2+dots+a_n)x + dots + (a_1a_2+a_1a_3+ dots + a_{n-1}a_n)x^2+dots + a_1a_2dots a_nx^n end{array}$
顯然, 一系列一元一次函數的乘積可以被簡化為母函數的形式. 易知, 我們可以將一元一次函數推廣到一元多次函數, 這裡不再贅述.

問題解決

接下來, 我們來解決一個問題, 求用 1 分, 2分, 3分的郵票貼出不同數值的方案數.
了解了代數解法中 $(1+x^4)$ 的意義, 那麼我們就可以寫出當前問題的母函數 G(x)
$egin{array}{l} G(x) = (1 + x + x^2 + dots + x^n) ( 1+x^2 + x^4 + dots + x^{2n})(1 + x^3 + x^6 + dots + x^{3n}) end{array}$
顯然, 對這個式子進行計算, 那麼得到的 $x^n$ 前的係數就是郵票價值為 n 時的組成方案數.

代碼

""" 1. 計算給定最大價值郵票數額, 計算出小於給定價值的郵票的組成方案數的集合. 2. 我們不保存冪函數的次冪, 只保存冪函數的係數. 因為次冪可以通過下標的枚舉來控制."""def generating_func(value): value += 1 # 我們在數組中需要使用到價值為 value的組成方案數, 故需要防止溢出 count = [1] * value # 由表達式可知, 第一個表達式的每一個冪函數的係數都為 1 temp = [0] * value # 存儲中間結果 for expression_index in range(2, value): # 只需要計算第二個表達式以及之後的表達式 for item_index in range(0, value): # 枚舉當前表達式所有冪函數的係數 for mul_item_index in range(0, value, expression_index): # 枚舉相乘的表達式的冪函數的所有係數 if item_index + mul_item_index < value: temp[mul_item_index + item_index] += count[item_index] # 更新對應次冪的係數值 count = temp.copy() # 保存計算完前 expression_index 個表達式的計算結果. temp = [0] * value return count

其他應用

我們對於指定郵票數額的構造可以看做一系列一定數量的一些郵票數額的加法, 反過來看, 那麼其也可以對應成整數的拆分, 例如 7 = 1 + 2 + 4. 所以冪函數的係數也可以看做整數的拆分數.

總結

本文介紹的方法只適用於母函數的入門, 如果還需要深入學習, 需要點擊下面的鏈接, 有更多的資料可以學習.

參考文獻

母函數（Generating function）詳解 - TankyWoowww.wutianqi.comdp 母函數入門 + 模板 - CSDN博客blog.csdn.net
推薦閱讀：

※你無意中發現過哪些圖靈完全的系統？
※常見面試題整理--Python概念篇
※論Python asyncio的一個坑

TAG:编程 |