离散数学之把妹要诀

太过爱你忘了你带给我的痛 2022-09-25 03:22 148阅读 0赞

**题目来源：**

http://mp.weixin.qq.com/s?\_\_biz=MzI1MTIzMzI2MA==&mid=2650560189&idx=1&sn=2a5b8b80947b072e895786e1b32f0f07&scene=0\#wechat\_redirect

以上的排序表解读为：男生1最中意女生C，次中意女生B，次次中意女生E……

以此类推……

在五男五女全部成功脱光之后（假设都在圈子内部解决），定义一个unstable matching为：如果存在一对不是情侣的男女符合以下情况：

对于该男，该女在他的preference列表中处于现任女友的前面，对于该女，该男在他的preference列表中亦处于现任男友的前面，那么这对男女必然有私奔的倾向……

这样的情景即为unstable matching。反之，若不存在这样一对有私奔倾向的男女，即为stable matching。

问题是：是否在任何情况下，即不论各位的preference列表如何变化，只要男女数量相同，总是存在一个stable matching。 （当然，搅基之类的，是不可以的……）

以上是题目;

我写了一下大纲，没写出算法2333

package 离散数学之把妹要诀;
    
    public class Main {
    	public static void main(String[] args) {
    		
    	}
    }
    class boy{
    	int lover=5;
    	int number;
    	char bestLoverNumber;
    	char []preference=new char[lover];
    	public boy(){}
    	public boy(String st){
    		
    		for(int i=0;i<5;i++){
    			preference[i]=st.charAt(i);
    		}
    	}
    	public void set(int number){
    		this.number=number;
    	}
    }
    class girl{
    	char number;	//个人编号
    	int bestLoverNumber;	//最喜欢的人的编号
    	int lover=5;	//相亲人数
    	int [] preference=new int [lover];
    	public girl(){}
    	public girl(String st){
    		for(int i=0;i<5;i++){
    			preference[i]=(((int)st.charAt(i))-48);
    		}
    	}
    	public void set(char number){
    		this.number=number;
    	}
    }
    class match{
    	boy[] bo=new boy[]{new boy("CBEAD"),new boy("ABECD"),new boy("DCBAE"),new boy("ACDBE"),new boy("ABDEC")};
    	girl[] gi=new girl[]{new girl("35214"),new girl("52143"),new girl("43512"),new girl("12345"),new girl("23415")};
    	public void setnumber(){
    		//初始化男女数组
    		for(int i=0;i<5;i++){
    			bo[i].set(i+1);
    			bo[i].bestLoverNumber=bo[i].preference[0];
    			char letter=(char)('A'+i);
    			gi[i].set(letter);
    			gi[i].bestLoverNumber=bo[i].preference[0];
    		}
    	}
    	public void match_man(){
    		//这里写匹配
    	}
    }

**稳定排序的算法如下：**

1962年，Gale 和 Shapley 证明了stable matching是一定存在的。

首先他们给出了一个算法：

第一天早上：所有男生都向自己最中意的女生表白。

第一天中午：每个女生都被表白了n次（可能是0次）之后，拒绝了相对不太中意的那n-1位，hold住其中最中意的那位……即暂时不答应也不拒绝

第一天晚上，被拒绝的男生们在自己的preference列表中划掉了那个拒绝他的人……

第二天早上：所有没有被hold住的男生都向自己最中意的女生（无视已经被划掉的）表白。

第二天中午：女生们在那些向她表白的男生和已经hold住的那男生中选择最中意的一位，拒绝掉其他的。

第二天晚上：被拒绝的男生们在自己的preference列表中划掉拒绝了自己的人……

第三天，重复同样的过程……

第四天……

以上的排序表解读为：男生1最中意女生C，次中意女生B，次次中意女生E……