Summorial

Triangular Number

「三角數」。nk=1 k = 1 + 2 + ... + n。

數學家稱作三角數。英文俗稱summorial。中文俗稱階加。

Faulhaber's Formula

階加已有許多經典公式,不必逐項相加。例如高斯梯形公式:1+2+...+n = n(n-1)/2,例如正方形的L形分解:1+3+5+7+...+(2n-1) = n²。

1¹ + 2¹ + ... + n¹ = n(n+1)/2
1² + 2² + ... + n² = n(n+1)(2n+1)/6
1³ + 2³ + ... + n³ = (1+2+...+n)² = sum(n)²

Factorial

Factorial

「階乘」。n! = 1 × 2 × ... × n。

Falling Factorial / Rising Factorial

「下降階乘」。n = n × (n-1) × ...。總共k個數。

「上升階乘」。n = n × (n+1) × ...。總共k個數。

Stirling's Formula

階乘已有快速近似公式,不必逐項相乘。

http://www.stat.ualberta.ca/people/schmu/preprints/factorial.pdf

n! ≈ sqrt(2πn) (n/e)ⁿ

UVa 1185

數學公式

Wilson's Theorem:階乘推廣成餘數。

Legendre's Formula:階乘推廣成p進數。

luogu P5282 P5702

Permutation

前言

電腦擅於處理大量資料。處理大量資料,除了大家熟悉的排序和搜尋以外,其實還有排列和組合。

有些問題需要找到最好的排列組合方式。例如求最佳排列的問題Travelling Salesman Problem、Assignment Problem,例如求最佳組合的問題Partition Problem、Knapsack Problem。

想要解決這些問題,最簡單的方法就是枚舉法:枚舉所有可能的排列、組合,一一驗證,從中找到最好的排列、組合。

排列

此處的排列是名詞。排列就是交換位置。排列也是交換順序。

例如有五筆資料   ●★■▲◆

這是其中一種排列  ▲●◆★■
這也是其中一種排列 ●★■▲◆

設定編號,變成數字,方便記載。

          12345
例如有五筆資料   ●★■▲◆

這是其中一種排列  41523
這也是其中一種排列 12345

排列(定量版本)

取出定量、進行排列。

例如有五筆資料      12345

取三筆資料的其中一種排列 415
取三筆資料的其中一種排列 523
取三筆資料的其中一種排列 235

統計所有排列(定量版本)

數學符號是P(n,k)。n個取出k個,相異排列數量。

數學公式是P(n,k) = n = n! ÷ (n-k)!。

更進階的情況,例如「庭院深深深幾許」、「男女相間坐成一圈」,基本上是益智遊戲,這裡就不提了。

UVa 12257

編號所有排列

http://en.wikipedia.org/wiki/Factorial_number_system

Lehmer Code又稱Cantor Expansion:右方數字個數,階乘,作為數量級。右方較小的、尚未出現的數字個數,作為位數。

UVa 941 11525 417 11027 luogu P5367

枚舉所有排列

http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

Backtracking:遞迴填入數字。可以得到字典順序。

Steinhaus-Johnson-Trotter Algorithm:以Gray Code的順序兩兩交換。

Heap's Algorithm:判斷奇偶,適時交換。

下一個排列

給定其中一個排列,按照字典順序,找到下一個排列。

把數字想像成數字卡。先拿起一張低位數的數字卡,再利用手上的數字卡,嘗試重新拼出比原本更大一點點的數值(下一個排列)。如果拼不出來,就再多拿起一張數字卡,再拼一遍。

可以直接使用STL的next_permutation()。

UVa 146 845

隨機排列

一群數字不按順序排好、打亂順序。排序的相反。

從所有排列取出一種排列。每種排列的出現機率都一樣。

隨機排列經常用於隨機演算法,避免輸入資料成為worst case,降低演算法的時間複雜度。隨機排列也經常用於製造隨機輸入,用來測試程式是否穩健。

Fisher-Yates Shuffle:跟後方任意數字交換、或者不交換。時間複雜度O(N)。

可以直接使用STL的shuffle()。

Consecutive Ones Problem

N個人,排成一直線。限制某些人一定要排在一起,這樣的限制有許多組,必須同時滿足;如果限制過多,也可能無解。問有幾種排法、列出所有排法。

建立一個矩陣。令一個row代表一個限制,要排一起的人標1。兩個column交換,就等於一直線中的兩個人對調位置。不斷交換column,當每個row各自都連成連續的1,就形成一組解了!

為了快速解決這個問題,而發明了PQ Tree資料結構,時間複雜度O(NM+NP),N是人數,M是限制數量,P是排法數量。

由於PQ Tree非常噁心,這裡不再多提,有興趣的讀者請自行搜尋資料。

ICPC 3511 UVa 11993

Consecutive Ones Submatrix Problem

NP-hard。

Gray Code

Gray Code

「格雷碼」。一串數列,0到2ᴺ - 1的整數各出現一次,表示成二進位。相鄰數字恰有一個位數不同,可能是1變0、0變1。數列頭尾視作相鄰。符合條件的數列,通常有許多種。

[N = 0] 0
[N = 1] 0 1
[N = 2] 00 01 11 10
[N = 3] 000 001 011 010 110 111 101 100

N維空間,正N方體,邊長為1,靠在原點上,貼齊座標軸,置於第一象限。任選一個頂點開始,沿邊行走,經過每個頂點各一次,走完一圈回到起點。途經座標就是一組Gray Code!

  011         111        011________ 111
     /|      /|            /        |   
001 / |  101/ |        001/_______  |   
   |  |_____|_|110       010______|_|110
   | 010    |              /      |     
000|________|100       000/_______|100  

Gray Code的遞推與遞歸

Gray Code可以用遞推法解釋:

GrayCode(n-1)的每個數字,最高位數添0。
GrayCode(n-1)的每個數字,頭尾顛倒,最高位數添1。
兩者銜接起來就是GrayCode(n)。

Gray Code可以用遞歸法解釋:

GrayCode(n)的每個數字,分成兩類。
第一類最高位數是0,拿掉最高位數即是GrayCode(n-1)。
第二類最高位數是1,拿掉最高位數即是GrayCode(n-1)。

也可以用最低位數為主,得到順序不同的Gray Code。

生成Gray Code

偶數項數字,由上一個數字,改變最低位的1的更高位數而得;奇數項數字,由上一個數字,改變最低位數而得。

不知如何解釋的方法。

Gray Code的應用

Tower of Hanoi河內塔的解法順序就是Gray Code!

Chinese Ring Puzzle九連環的解法順序就是Gray Code!

UVa 10455 11535

推廣到高維度

Gray Code可以推廣到高維度。比方說二維的情況下,Gray Code是一個方陣,上下左右皆循環,四方向相鄰數字恰有一個位數不相同。符合條件的方陣,通常有許多種。

[N = 0] 0
[N = 1] 0 1
        1 0
[N = 2] 00 01 11 10
        01 11 10 00
        11 10 00 01
        10 00 01 11

Combination

組合(子集合)

一堆東西,挑出其中幾個。可以全部都挑,也可以什麼都不挑。

組合就是挑選。組合就是剔除。無關順序。

例如有五筆資料    ●★■▲◆

這是其中一種組合   ★■◆
這和方才是同一種組合 ◆★■
這是其中一種組合   ▲
這是其中一種組合   ●★■▲◆
這是其中一種組合   nothing

組合(定量版本)

取出定量。

例如有五筆資料      ●★■▲◆

取三筆資料的其中一種組合 ★■◆
取三筆資料的其中一種組合 ●★■
取三筆資料的其中一種組合 ■▲◆

統計所有組合(定量版本)

數學符號是C(n,k)。n個取出k個,相異組合數量。

數學公式是C(n,k) = n ÷ 1 = n! ÷ (n-k)! ÷ k!。

編號所有組合

一個二進位數字,可以代表一個子集合。

       0       1      2     3       4
U = {lemon, orange, lime, apple, banana};

     43210
二進位數字01010,即是子集合 {orange, apple}
二進位數字00001,即是子集合 {lemon}
二進位數字00000,即是子集合 { }

實作程式碼時,運用資料結構「Bitset」或「整數」儲存一種組合,可以節省空間。運用程式語言的「Bitwise Operation」語法,可以節省時間。

枚舉所有組合

http://www.applied-math.org/subset.pdf

字典順序:數字由小到大。

000
001
010
011
100
101
110
111

Gray Code:相鄰數字僅改動一個位元。

000
001
011
010
110
111
101
100

Banker's Sequence:先枚舉小集合,再枚舉大集合;同樣大小的集合們之間,先枚舉數字大的(字典順序大的),再枚舉數字小的(字典順序小的)。

000 -- size = 0
100  \
010   | size = 1
001  /
110   \
101    | size = 2
011   /
111    -- size = 3

枚舉所有組合(定量版本)

Gosper's Hack:利用位元運算,快速得到下一個組合。

00111
01011
01101
01110
10011
10101
10110
11001
11010
11100

luogu P1441

下一個組合(定量版本)

給定其中一個組合,按照字典順序,找到下一個組合。

不知名的方法:利用位元運算,快速得到下一個組合。

隨機組合(定量版本)

從所有組合取出一種組合。每種組合的出現機率都一樣。

Reservoir Sampling:依序讀取數字,取代當下組合的任意數字,或者不取代。online演算法,當下組合是當下答案。時間複雜度O(N)。

Li's Algorithm:改良版本。跳躍讀取數字,節省時間。背後原理是幾何分布。時間複雜度O(K + Klog(N/K)),到達理論下限。

可以直接使用STL的sample()。

Inclusion-Exclusion Principle

Inclusion-Exclusion Principle(PIE)

繁中「取捨原理」「排容原理」、簡中「容斥原理」。

【待補文字】

UVa 10325 11806 10458

數學公式

Trailing 0s of N!:判斷是否能整除10ⁿ,n最大是多少。

UVa 1185 10061 701 10212 12689