permutation

前言

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

有些問題需要找到最好的排列組合方式。例如求最佳排列的問題 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

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';
}

枚舉所有組合

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

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

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

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 組合。

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

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