离散单射满射双射

全栈程序员站长

发布于 2022-06-28 16:12:49

1.8K0

发布于 2022-06-28 16:12:49

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

单射双射满射

阐述一下什么是单射，双射，满射 1.单射：对于每一个不同的x都有不同的y，即 x1!=x2–>y1!+y2 条件：|X|<=|Y| 2.满射：对于每一个y都有x与之对应条件：|Y|<=|X| 3.双射：既是单射又是满射条件：|X|=|Y|

代码实现

通过map函数建立映射 1.单射：

map<int, int> BuildInjection(vector<int> src, vector<int> dst)
{ 
   
    map<int, int> injection;
    for (int i = 0; i < src.size(); ++i) { 
   
        injection[src[i]]=dst[i];
    }
    return injection;
}

因为是单射，所以|X|<|Y|，我们通过map函数建立键值对，来实现函数中的映射关系，所以我们形成映射的时候，只需要对于每一个X都有不同的Y即可，所以我们通过for循环，因为X<Y，所以取X的size()，为临界点，插入键值对。 2.满射：

map<int, int> BuildSurjection(vector<int> src, vector<int> dst)
{ 
   
    map<int, int> surjection;
    for (int i = 0; i < dst.size(); ++i) { 
   
        surjection[src[i]]=dst[i];
    }
    return surjection;
}

同理，通过src作为临界点进行便利 3.双射：

map<int, int> BuildBijection(vector<int> src, vector<int> dst)
{ 
   
    map<int, int> bijection;
    vector<int>::iterator iter;
    vector<int>::iterator iter1;
    for(iter=src.begin(),iter1=dst.begin();iter!=src.end()&&iter1!=dst.end();iter++,iter1++){ 
   
        bijection[*iter]=*iter1;
    }
    return bijection;
}

双射就是一一对应，每一个都不能有重复，所以通过迭代器的++来输入不同的键值对。

判断是否是单射，满射，双射

1.验证单射：

bool ValidateInjection(vector<int> src, vector<int> dst, map<int, int> injection)
{ 
   
    bool bIsInjection = false;
    int size1=0;
    set<int> s;
    map<int ,int>::iterator iter;
    for (iter=injection.begin();iter!=injection.end();iter++,size1++) { 
   
        s.insert(iter->second);
    }
    if(size1==s.size()) bIsInjection= true;
    return bIsInjection;
}

set函数，是一个集合，他的作用是对于插入的数据进行排序以及去重，所以我们把Y值插入到s中观察是否有相同的数据，只需要判断键值对的数量以及集合的长度是否相等即可 2.验证满射

bool ValidateSurjection(vector<int> src, vector<int> dst, map<int, int> surjection)
{ 
   
    bool bIsSurjection = false;
    //请把你的代码写在下方，请勿修改任何已有代码
    int temp=dst.size();
    set<int> s;
    map<int ,int>::iterator iter;
    for (iter=surjection.begin();iter!=surjection.end();iter++)
    { 
   
        temp--;
    }
    if(temp==0) bIsSurjection= true;
    //
    return bIsSurjection;
}

我们对键值对进行遍历，每次都把Y中的长度-1，直至遍历完成，如果长度为0，就是满射，如果不是就不是满射 3.验证双射：

bool ValidateBijection(vector<int> src, vector<int> dst, map<int, int> bijection)
{ 
   
    bool bBiSurjection = false;
    //请把你的代码写在下方，请勿修改任何已有代码
    int temp=dst.size();
    bBiSurjection= true;
    map<int,int>::iterator iter;
    for (int i = 0; i < src.size(); ++i) { 
   
        iter=bijection.find(src[i]);
        if(iter==bijection.end()){ 
   
            bBiSurjection= false;
        }
    }
    set<int> s;

    for (iter=bijection.begin();iter!=bijection.end();iter++) { 
   
        s.insert(iter->second);
    }
    if(temp!=s.size()){ 
   
        bBiSurjection = false;
    }
    //
    return bBiSurjection;
}

验证双射，双射一一对应，我们遍历X，在map中寻找X的键值对，有键值对就证明是对的，一旦找到没有键值对的X，就不是双射。再遍历Y，看Y中是否有相同值，有就不是双射

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/132811.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年6月1，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法