前言

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

有些問題需要找到最好的排列組合方式。例如求最佳排列的問題travelling salesman problem、assignment problem，例如求最佳組合的問題partition problem、knapsack problem。

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

permutation

數學名詞「permutation」，英文口語「arrangement」。

「排列」。此處的排列是物件，不是函數。

排列就是交換位置。排列也是交換順序。

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

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

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

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

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

k-permutation

挑出k個。

例如有五筆資料　　　　　　12345

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

編號所有排列

N筆資料的所有排列一共N!種。

一個階乘進位數字，可以代表一個排列。

Lehmer code又稱Cantor expansion：右方數字個數，階乘，作為數量級。右方較小的、尚未出現的數字個數，作為位數。

const int N = 5; int a[N] = {4, 1, 5, 2, 3}; int c[N+1]; // binary indexed tree int permutation_to_index() { int fac = 1, n = 0; for (int i=1; i<=N; ++i) { int sum = 0; for (int x=a[N-i]; x; x-=x&-x) sum += c[x]; n += fac * sum; fac *= i; for (int x=a[N-i]; x<=N; x+=x&-x) ++c[x]; } return n; } const int N = 5; const int lgN = log2(N); int a[N] = {1, 2, 3, 4, 5}; // sorted int c[N+1]; // binary indexed tree void index_to_permutation(int n) { memset(c, 0, sizeof(c)); int fac = 1; for (int i=1; i<N; i++) fac *= i; for (int i=1; i<=N; i++) { int digit = n / fac; n %= fac; if (N-i) fac /= (N-i); // binary search int ans = 0; for (int k=1<<lgN; k; k>>=1) { if (ans+k >= N) continue; int sum = 0; for (int x=ans+k; x; x-=x&-x) sum += c[x]; if (ans+k - sum <= digit) ans += k; } for (int x=ans+1; x<=N; x+=x&-x) c[x]++; cout << a[ans]; } }

UVa 941 11525 417 11027 luogu P5367

枚舉所有排列

backtracking：遞迴填入數字。可以得到字典順序。

int a[5]; bool used[5]; void print(int N) { for (int i=0; i<N; ++i) cout << a[i]; cout << '\n'; } void backtrack(int n, int N) { if (n == N) {print(N); return;} for (int i=0; i<N; i++) if (!used[i]) { used[i] = true; a[n] = i; backtrack(n+1, N); used[i] = false; } } void enumerate_permutations(int N) { for (int i=0; i<N; i++) used[i] = false; backtrack(0, N); }

Steinhaus–Johnson–Trotter algorithm：以Gray code的順序兩兩交換。

https://rosettacode.org/wiki/Permutations_by_swapping

Heap's algorithm：判斷奇偶，適時交換。

const int N = 5; int a[N] = {1, 2, 3, 4, 5}; int c[N]; // factorial number system void print() { for (int i=0; i<N; ++i) cout << a[i]; cout << '\n'; } void enumerate_permutations() { for (int i=0; i<N; ++i) c[i] = 0; print(); for (int i=0; i<N; ) if (c[i] < i) { swap(a[i & 1 ? c[i] : 0], a[i]); c[i]++; i = 0; print(); } else c[i++] = 0; }

下一個排列

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

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

可以直接使用C++標準函式庫的next_permutation()。

const int N = 5; int a[N] = {1, 2, 3, 4, 5}; void print() { for (int i=0; i<N; ++i) cout << a[i]; cout << '\n'; } bool next_permutation() { for (int i=N-1; i>0; i--) if (a[i-1] < a[i]) { int j = N-1; while (a[i-1] >= a[j]) j--; swap(a[i-1], a[j]); reverse(a+i, a+N); return true; } // reverse(a, a+N); // 從頭開始循環 return false; } void enumerate_permutations() { do print(); while (next_permutation()); }

UVa 146 845

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

「格雷碼」。一串數列，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的更高位數而得；奇數項數字，由上一個數字，改變最低位數而得。

// 0 < N < 32 for (unsigned int i = 0, c = 0; i < (1 << N); i += 2) { cout << (c ^= ((c & -c) << 1)); cout << (c ^= 1); }

不知如何解釋的方法。

// 0 < N < 32 for (unsigned int i = 0; i < (1 << N); i++) cout << (i ^ (i >> 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（subset）

數學名詞「combination」，英文口語「selection」。

「組合」。意義等同「子集合」。

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

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

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

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

k-combination

挑出k個。

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

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

編號所有組合

N筆資料的所有組合一共2ᴺ種。

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

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

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

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

const int N = 5; // 數量 void print(int comb) { cout << '{'; for (int i=0; i<N; ++i) if (comb & (1 << i)) cout << 1; else cout << 0; cout << '}' << '\n'; }

枚舉所有組合

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

000
001
010
011
100
101
110
111

for (int i=0; i<(1<<N); i++) print(i);

Gray code：相鄰數字僅改動一個位元。

000
001
011
010
110
111
101
100

for (int i=0; i<(1<<N); i++) print(i^(i>>1));

Banker's sequence：先枚舉小集合，再枚舉大集合；同樣大小的集合們之間，先枚舉數字大的（字典順序大的），再枚舉數字小的（字典順序小的）。

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

https://rosettacode.org/wiki/Banker's_algorithm

枚舉所有k組合

Gosper's hack：利用位元運算，快速得到下一個k組合。

00111
01011
01101
01110
10011
10101
10110
11001
11010
11100

for (unsigned int comb = (1 << K) - 1; comb < 1 << N;) { print(comb); unsigned int x = comb & -comb, y = comb + x; comb = ((comb ^ y) / x >> 2) | y; }

luogu P1441

下一個k組合

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

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

void next_combination(unsigned int comb) { unsigned int t = (comb | (comb - 1)) + 1; comb = t | ((((t & -t) / (comb & -comb)) >> 1) - 1); print(comb); }

inclusion–exclusion principle（PIE）

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

枚舉所有子集合，但是每個子集合有正負號之別──奇數個集合的交集是正號、偶數個集合的交集是負號。

void inclusion_exclusion_principle(int N) { for (int comb = 0; comb < 1<<N; ++comb) { int c = 0; // size of set for (int i=0; i<N; ++i) if (comb & (1 << i)) c++; if (c & 1) cout << "negative"; else cout << "positive"; } }

範例：1到100當中不可被3或5或8整除的整數有幾個

3、5、8均兩兩互質。

int array[3] = {3, 5, 8}; // 取捨原理，sign是正負號，divisor是各種可能的除數 int backtrack(int n, int sign, int divisor) { // 製作了其中一個答案 if (n == 3) return sign * (100 / divisor); int total = 0; // 不選。正負號維持不變，除數維持不變。 // solution[n] = false; total += backtrack(n+1, sign, divisor); // 選。須變號，並逐步累計除數。 // 因逐步累計除數，故不需要具體記錄選到的數字 // solution[n] = true; total += backtrack(n+1, -sign, divisor * array[n]); return total; } void inclusion_exclusion() { cout << "1到100當中不可被3或5或8整除的整數"; cout << "有" << backtrack(0, +1, 1) << "個"; }

考慮數字之間不互質的情況。

int array[5] = {3, 5, 6, 7, 9}; // 最大公因數 int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } // 最小公倍數 int lcm(int a, int b) { return a / gcd(a, b) * b; } // 精簡過後的取捨原理程式碼，divisor是各種可能的除數 int backtrack(int n, int divisor) { if (n == 5) return 100 / divisor; return backtrack(n+1, divisor) - backtrack(n+1, lcm(divisor, array[n])); } void inclusion_exclusion() { cout << "1到100當中不可被3或5或6或7或9整除的整數"; cout << "有" << backtrack(0, 1) << "個"; }

另一種枚舉方式。

int array[5] = {3, 5, 6, 7, 9}; int backtrack(int n, int divisor) { int total = 0; total += 100 / divisor; // 目前湊出來的集合 // 繼續枚舉之後的數字，記得變號 for (int i=n; i<5; ++i) total -= backtrack(i+1, lcm(divisor, array[i])); return total; } void inclusion_exclusion() { cout << "1到100當中不可被3或5或6或7或9整除的整數"; cout << "有" << backtrack(0, 1) << "個"; }

UVa 10325 11806 10458