【离散数学上机】T235，T236
T235题目：输入集合A和B，输出A到B上的所有单射函数。
问题描述
给定非空数字集合A和B，求出集合A到集合B上的所有单射函数。
输入格式
第一行输入m和n（空格间隔），分别为集合A和集合B中的元素个数；
第二行输入非空数字集合A，每个元素之间用空格间隔；
第三行输入非空数字集合B，每个元素之间用空格间隔；
输出格式
输出每一行为集合A到集合B的一个构成单射函数的二元关系，按二元关系的基数大小从小到大输出所有二元关系，相同基数的二元关系按序偶中元素的字典序排列。
样例输入
2 2
1 2
3 4
样例输出
{<1,3>,<2,4>}
{<1,4>,<2,3>}
在T234基础上，保证加入q集合中元素不重复即可，前者链接见下：
【xdoj-离散线上练习H】T234（C++）-CSDN博客
#include<bits/stdc++.h>
using namespace std;int main()
{//预处理：利用优先队列将集合中元素从小到大放进数组A，B中int m, n, cur;cin>>m>>n;priority_queue<int>pq; vector<int>A(m);vector<int>B(n);for(int i=0; i<m; i++) {cin>>cur; pq.push(cur);}for(int i=1; i<=m; i++) {A[m-i] = pq.top(); pq.pop(); }for(int i=0; i<n; i++) {cin>>cur; pq.push(cur);}for(int i=1; i<=n; i++) {B[n-i] = pq.top(); pq.pop(); }//观察输出样例：每行输出均有A中全部元素，B对应元素每行只有一处变化vector<int>q(m);//q[i]携带了当前映射关系中A[i]对应的集合B中元素//为什么用递归：因为A中元素数量不确定，事实上，如果用for循环嵌套，那么for循环的数量为 m，这是不能在确定的代码中实现的auto dfs = [&](auto& dfs, int cnt) -> void{if(cnt == m)//递归终止条件{cout<<"{";for(int i=0; i<m; i++){cout<<"<"<<A[i]<<","<<q[i]<<">"; if(i == m-1) cout<<"}"<<endl;else cout<<",";}return; }else{//继续递归for(int i=0; i<n; i++){//保证q中的元素不重复int k=0;for( ; k<cnt; k++){if(q[k] == B[i]) break;} if(k == cnt) {q[cnt] = B[i];dfs(dfs, cnt+1);} } return;}};dfs(dfs, 0);return 0;
}T236题目：输入集合A和B，输出A到B上的所有满射函数。
只需将dfs函数替换成如下形式
auto dfs = [&](auto& dfs, int cnt) -> void{if(cnt == m)//递归终止条件{set<int>st;for(int i=0; i<m; i++){st.insert(q[i]);}if(st.size() == n){cout<<"{";for(int i=0; i<m; i++){cout<<"<"<<A[i]<<","<<q[i]<<">"; if(i == m-1) cout<<"}"<<endl;else cout<<",";}}return; }else{//继续递归for(int i=0; i<n; i++){q[cnt] = B[i];dfs(dfs, cnt+1); } return;}};T237题目：输入集合A和B，输出A到B上的所有双射函数。
将dfs换成这个就成
auto dfs = [&](auto& dfs, int cnt) -> void{if(cnt == m)//递归终止条件{set<int>st;for(int i=0; i<m; i++){st.insert(q[i]);}if(st.size() == n){cout<<"{";for(int i=0; i<m; i++){cout<<"<"<<A[i]<<","<<q[i]<<">"; if(i == m-1) cout<<"}"<<endl;else cout<<",";}}return; }else{//继续递归for(int i=0; i<n; i++){//保证q中的元素不重复int k=0;for( ; k<cnt; k++){if(q[k] == B[i]) break;} if(k == cnt) {q[cnt] = B[i];dfs(dfs, cnt+1);} } return;}};