# 枚舉2
by:hush
---
## 枚舉子集(subset)
----
- 什麼是子集？
從一個母集合裡挑若干個元素，可以全挑也可以不挑
(集合沒有順序也不重複)
----
- 舉例：
定義一個集合$S=\{1,3,4,6\}$
則 $\{4,1\}或\{1,3,4,6\}或\{ \}$ 為$S$的子集
而 $\{1,2\}或\{1,3,4,6,8\}$ 不是
----
- 實作方法：
1. 遞迴枚舉1
2. 遞迴枚舉2
3. 位元枚舉（迴圈版）
時間複雜度都是$O(2^n)$
----
- 遞迴枚舉1：
若共有$n$個元素，當下選到第$k$個，遞迴枚舉下一個元素為第$k+1$ ~ $n$的情況，從$0$(代表空的元素)開始遞迴
----
code:
```cpp=
#include<bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
vector<int> a(25);
vector<bool> in(25,0);
int n;
void subset(int k)
{
if (k==n+1) //枚舉結束
{
for (int i=1;i<=n;i++)
if (in[i]) cout << a[i] <<' ';
cout << '\n';
return;
}
in[k]=1;
for (int i=k+1;i<=n+1;i++) subset(i);
in[k]=0;
}
signed main()
{
//colinorz;
cin >> n;
for (int i=1;i<=n;i++) cin >> a[i];
subset(0);
}
```
----
- 遞迴枚舉2：
若共有$n$個元素，當下已決定前$k-1$個元素是否在子集合內，則分別枚舉第$k$個元素存在以及不存在的情況(我通常使用0-base寫法)
----
code:
```cpp=10
//前面一樣
void subset(int k)
{
if (k==n) //枚舉結束
{
for (int i=0;i<n;i++)
if (in[i]) cout << a[i] <<' ';
cout << '\n';
return;
}
in[k]=1; //第k個元素存在
subset(i);
in[k]=0; //記得設回不存在
subset(i);
}
signed main()
{
//colinorz;
cin >> n;
for (int i=0;i<n;i++) cin >> a[i];
subset(0);
}
```
----
- 迴圈枚舉：
要用到一些位元運算的東西([點這裡自學](https://apcs.guide/courses/beginner/tricks/binary-operator))
概念是把子集合用一個$x$整數來表示$(1\le x\lt 2^{|S|})$，$x$二進位表示中的第$k$位若為1，則第$k$個元素在子集合內
- 有$3$個元素的情況：
|$x$| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| - | - | - | - | - | - | - | - | - |
|$2^0$| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
|$2^1$| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
|$2^2$| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
----
code:
```cpp=10
//前面一樣
void subset()
{
for (int i=0;i<(1<<n);i++) //「a<<b」代表a*2^b
{
for (int j=0;j<n;j++)
if (i&(1<<j)) //第j個元素是否存在子集
{
cout << a[j] << ' ';
}
cout << endl;
}
}
signed main()
{
//colinorz;
cin >> n;
for (int i=0;i<n;i++) cin >> a[i];
subset();
}
```
----
- 練習題：
[CSES1623](https://cses.fi/problemset/task/1623)
----
- CSES1623題解：
枚舉所有子集，求子集合加總和補集合加總的差，取最小的差輸出
- 小技巧：
這題我會用遞迴枚舉而不是位元枚舉(迴圈)，原因是遞迴枚舉邊枚舉就可以邊算加總，而位元枚舉每個子集都要重算一次，速度較慢
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
int n,sum=0,cnt=0,ans=1e18;
vector<int> a(25);
void mind(int i)
{
if (i==n)
{
ans=min(ans,abs(cnt-(sum-cnt)));
return;
}
cnt+=a[i]; //枚舉在目前情況有包含a[i]的子集合
mind(i+1);
cnt-=a[i]; //枚舉不包含a[i]的
mind(i+1);
}
signed main()
{
//colinorz;
cin >> n;
for (int i=0;i<n;i++) cin >> a[i],sum+=a[i];
mind(0);
cout << ans <<'\n';
}
```
---
### 折半枚舉
----
$2^{20}\approx 1.04\times 10^6$ ||( nice )||
$2^{40}\approx 1.09\times 10^{12}$ ||( = = )||
----
直接看題目（[zj_a161](https://judge.cchs.chc.edu.tw/ShowProblem?problemid=a161)）：
- 輸入$n$個正整數$A_1$~$A_n$，和一個整數$P$
- 請計算$A$的各種子集合中，其加總值最接近$P$但不超過$P$的值是多少。
- $A_i, P\le 2^{60}$，$0 < n ≤ 38$
----
- $n=38$直接枚舉，$O(2^n)$肯定會TLE，所以：
1. 把$n$平分成兩堆，分別枚舉子集
$O(2^{n/2})$
2. 挑其中一堆進行排序
$O(2^{n/2}\cdot log(2^{n/2}))$
3. 遍歷另一堆，對已排序那堆二分搜
$O(2^{n/2}\cdot log(2^{n/2}))$
- 註：二分搜也可用雙指標代替，重點是要讓原本的$O(2^{\tfrac{n}{2}^2})$變更快
----
AC code:
```cpp=
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define colinroz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
vector<int> a(45);
vector<vector<int>> subset(5);
void enu(int cur,int l,int r,int sum=0) //[l,r)
{
if (l==r)
{
subset[cur].emplace_back(sum);
return;
}
enu(cur,l+1,r,sum+a[l]); //有a[l]
enu(cur,l+1,r,sum); //沒有
}
signed main()
{
//colinorz;
int n,p,ans=-1e18; cin >> n >> p;
for (int i=0;i<n;i++) cin >> a[i];
int mid=n/2+n%2;
enu(0,0,mid); enu(1,mid,n);
sort(subset[1].begin(),subset[1].end());
for (int& i : subset[0])
{
auto it=upper_bound(subset[1].begin(),subset[1].end(),p-i);
if (it==subset[1].cbegin()) continue; //.cbegin()代表常數iter
ans=max(ans,i+*(it-1));
}
cout << ans << endl;
}
```
---
## 枚舉排列
----
- 什麼是排列？
就是一個序列的各種順序（註：交換兩個值相同的元素還是同一種排列）
- 舉例：
序列$[4, 1, 2]$的所有排列有$[1, 2, 4]$, $[1, 4, 2]$, $[2, 1, 4]$, $[2, 4, 1]$, $[4, 1, 2]$, $[4, 2, 1]$
----
實作方法：
1. 手刻遞迴
2. STL函式
----
- 手刻函式：
改一下前面子集的**遞迴枚舉1**就可以了。
時間複雜度$O(n\times n!)$有點高，所以不常用。但有時候題目會逼你寫，所以建議還是要知道怎麼寫
----
code:
```cpp=
#include<bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
vector<int> a(25),now;
vector<bool> used(25,0);
int n;
void permutation(int k)
{
if (k==n) {
for (int i=0;i<n;i++) cout << now[i] << " \n"[i==n-1];
return ;
}
for (int i=0;i<n;i++) {
if(used[i]) continue ; //用過了就不能再用
now.push_back(a[i]);
used[i]=1;
permutation(k+1);
now.pop_back();
used[i]=0; //記得改回來！
}
}
signed main()
{
//colinorz;
cin >> n;
for (int i=0;i<n;i++) cin >> a[i];
permutation(0);
}
```
----
- STL函式：
**先排序**，然後用std::next_permutation函式。
時間複雜度$O(n!)$，不會把相同的值重複排序
----
code:
```cpp=12
//前面一樣
signed main()
{
//colinorz;
cin >> n;
for (int i=0;i<n;i++) cin >> a[i];
sort(a.begin(),a.begin()+n); //要先排序！！！
do
{
for (int i=0;i<n;i++) cout << a[i] << " \n"[i==n-1];
}while (next_permutation(a.begin(),a.begin()+n)); //行尾要分號！！！
}
```
----
- 練習題：
[cses1622](https://cses.fi/problemset/submit/1622/)
----
- cses1622 題解：
||首先理解題目意思，然後直接實作即可||
----
AC code:
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
string s;
signed main()
{
//colinorz;
cin >> s;
sort(s.begin(),s.end());
int cnt=0;
do
{
cnt++;
} while (next_permutation(s.begin(),s.end()));
cout << cnt << endl;
//枚舉完會變回原本順序
do
{
cout << s << endl;
} while (next_permutation(s.begin(),s.end()));
}
```
---
# 謝謝大家
{"description":"type: slide","title":"枚舉2","contributors":"[{\"id\":\"b49547c8-0e7f-46d0-99b2-8a45dfee8e90\",\"add\":6780,\"del\":356}]"}