【C++】競程筆記（枚舉）
===
[TOC]
程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。
---
枚舉就是窮舉法，把所有東西都列出來。
字典序（Lexicographic order）
---
字典序，就是依照字典中出現的先後順序進行排序。
主要是用來比較和已排序序列（特別是字串）的規則，按照類似於字典中單字排列的方式進行運算。
字典序是一種排序方法，其核心思想是透過比較兩個序列的元素，從第一個元素開始，逐步向後，直到找到第一個不同的元素，然後根據這個元素的順序決定兩個序列的先後。
如果一個序列是另一個序列的前綴，則較短的序列排在前面。這種排序方式與我們在字典中查找單字的順序類似，因此被稱為「字典序」。
1. 比較開頭字元
像是 "apple" 和 "banana"：
第一個字元：'a' vs 'b'
'a' 在字母表中排在 'b' 之前，因此 "apple" < "banana"。
2. 若前面字元都相同，則遍歷找兩字串中字元不同處去比較
像是 "apple" 和 "apricot"：
前兩個字元相同：'a' = 'a', 'p' = 'p'
第三個字元：'p' vs 'r'
'p' 在 'r' 之前，因此 "apple" < "apricot"。
3. 一字串較短，另一字串較長
像是 "app" 和 "apple"：
前三個字符相同：'a' = 'a', 'p' = 'p', 'p' = 'p'
"app" 到此結束，而 "apple" 還有後續字元，因此 "app" < "apple"。
### 字典序的比較規則
---
1. 兩字串首元素開始比較
2. 逐個元素比較：如果目前的元素相同，則繼續比較下一個元素。
3. 遇到不同元素時決定順序：如果在某個位置上，兩個元素不同，則較小元素所在的序列排在前面（「較小」取決於元素的順序，例如字母表順序或數值大小）。
4. 處理前綴情況：如果一個序列是另一個序列的前綴（即較短序列的所有元素與較長序列的前綴完全相同），則較短的序列排在前面。
next_permutation()
---
用已排序（由小到大）的資料，產生下一組排列。
語法：`std::next_permutation(first, last);`
> Returns true if the container could be rearranged to the to the lexicographical larger permutation.
From : [GeeksForGeeks](https://www.geeksforgeeks.org/stdnext_permutation-prev_permutation-c/)
若容器可重新排列為按字典序更大的排列，則回傳 true。
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = {1, 2, 3};
do {
for (int n : vec) cout << n << " ";
cout << endl;
} while (next_permutation(vec.begin(), vec.end()));
return 0;
}
```
輸出結果：
```
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
```
`3! = 1*2*3 = 6`，所以有六種情形，與輸出相符。
prev_permutation()
---
對已降冪排序（由大到小）的資料，產生上一組排序。
語法：`std::prev_permutataion(first, last)`
> Returns true if the container could be rearranged to the to the lexicographical smaller permutation.
From : [GeeksForGeeks](https://www.geeksforgeeks.org/stdnext_permutation-prev_permutation-c/)
若容器可重新排列為字典序較小的排列，則回傳 true。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v = {2, 1, 3};
do {
for (auto i: v) cout << i << " ";
cout << endl;
} while (prev_permutation(v.begin(), v.end()));
return 0;
}
```
輸出結果：
```
2 1 3
1 3 2
1 2 3
```
例題：彈珠配置
---
Source：https://zerojudge.tw/ShowProblem?problemid=d913
暴力窮舉法
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool is_solution(const vector<int>& perm, const vector<vector<int>>& guesses, const vector<int>& counts) {
for (int i = 0; i < 6; i++) {
int match_count = 0;
for (int j = 0; j < 6; j++) {
if (perm[j] == guesses[i][j]) {
match_count++;
}
}
if (match_count != counts[i]) {
return false;
}
}
return true;
}
int main() {
vector<vector<int>> guesses(6, vector<int>(6));
vector<int> counts(6);
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
cin >> guesses[i][j];
}
cin >> counts[i];
}
// 從最小排列 {1,2,3,4,5,6} 開始
vector<int> perm = {1, 2, 3, 4, 5, 6};
do {
// 若經函數處理過後發現是正確排列, 則輸出
if (is_solution(perm, guesses, counts)) {
for (int num : perm) {
cout << num << " ";
}
return 0;
}
} while (next_permutation(perm.begin(), perm.end()));
return 0;
}
```
這個題目很像最近很紅的 minecraft 猜方塊遊戲。老闆心中會秘密選定一個特定的排序，然後叫你去猜排序，而老闆只會告訴你有幾個正確的位置，但不會告訴你是哪一個位置正確。
假設先猜 1 2 3 4 5 6，而正確答案為 4 3 2 1 5 6，老闆會告訴你兩個數字對了。
有關題目敘述，輸入部分前六個數字是 1 2 3 4 5 6 的排列，第七個數字為彈珠在正確位置的個數。
然後輸出部分，則為字典序最小的排列。
再來因為 6! 排列，可能性只有 720 種，所以可以直接暴力解。
有關以上程式，`is_solution` 函數中的參數解釋如下：
* perm：目前測試的排列。
* guesses：前六次猜測的排列。
* counts：每一個猜測的正確位置數。
裡面用了雙層迴圈，主要用 perm 與 guesses 的六次猜測排列做比較，如果 `perm[j]` 跟 `guesses[i][j]` 的位置相同，則 `match_count ++`，然後經過一輪測試過後，發現 `match_count != count`（當前測試排列的正確位置數與彈珠的正確位置數不相等），就直接 false，換下一組排列，依此類推。
集合（Set）
---
若要列舉 $\{0, 1, \cdots, N - 1\}$ 的一個子集合，只需列舉 $0$ 到 $2^{N-1}$ 的所有整數。
C++ STL 中的 `<set>` 為一個關聯式容器，`<set>` 容器中儲存的元素型態必須符合以下條件：
1. 元素型態必須可以比較大小。
2. 元素型態必須可以被複製和指定。
:::info
在 C++ STL 中，關聯式容器（associative containers）是一類特殊的容器，透過鍵（key）、值（value）的關聯方式來儲存和管理元素。與序列式容器（如 vector、list）按照元素插入的順序來存儲元素不同，關聯式容器中的元素是根據 key 自動排序的，使得查找、插入和刪除操作能在時間複雜度 $O(log n)$ 內完成。
:::
特性：
* 唯一性：set 中的元素是唯一的，重複的元素將被忽略。
* 自動排序：元素會依照特定的排序準則（預設為升序）自動排列。
* 不可修改：一旦元素插入 set，其值不可直接修改，如需更改，需先刪除舊元素，再插入新元素。
語法：
```cpp
#include <set>
```
```cpp
set<T, comp> s;
```
T：集合中元素的資料型態。
s：集合的名稱。
comp：為 binary predicate function（二元謂詞函數：有兩個參數並回傳 bool 的函數或函數物件），告訴 set 如何比較兩個元素。這東西是 optional 的，如果沒有提供，則集合按升序排序。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
// 建立空集合
// Creating an empty set
set<int> s1;
// 建立一個來自初始化列表的集合
// Creating a set from an initializer list
set<int> s2 = {5, 1, 3, 2, 4};
for (auto i : s2)
cout << i << " ";
return 0;
}
```
output：
```
1 2 3 4 5
```
E.g. Source：https://www.geeksforgeeks.org/set-in-cpp-stl/
常用運算：
假設集合名字叫 set1。
* set1.insert(element)：插入某元素。
* set1.erase(element)：刪除某元素。
* set1.find(element)：查找某元素。
* set1.size()：回傳容器 set1 的長度（意即總元素數量）。
* set1.empty()：檢查容器 set1 是否為空。
參考資料
===
[枚舉 - NTUCPC Guide](https://guide.ntucpc.org/BasicAlgorithm/enumerate/)
[C++ 容器类 <set> | 菜鸟教程](https://www.runoob.com/cplusplus/cpp-libs-set.html)
[Set in C++ STL - GeeksforGeeks](https://www.geeksforgeeks.org/set-in-cpp-stl/)
Sign in with Wallet
Connect another wallet