Preface:
Recently, I was asked to write an algorithm about stable marriage. Stable marriage is a classic problem. I will not describe it here. You can find a lot on the Internet. A famous algorithm to solve the stable marriage problem is G-S algorithm, also known as delay recognition algorithm, which will not be described in detail. This algorithm can only reach a single optimal solution. Not long ago, in a book, we saw an algorithm (exhaustive method) for finding all possible solutions of stable matching. These days due to the new pneumonia lead to special leisure (hope that the pneumonia will soon end), so I plan to write about it.

Specific method (implemented in C + +):

1. Algorithm idea:
First, find a perfect match, and then judge whether there are unstable factors in the perfect match. If there are, discard the perfect match (that is, the perfect match is not a stable match). If there are no unstable factors, output the perfect match (the perfect match is a stable match). Then continue to find the next perfect match, and judge

2. Specific code:
① First, define a data structure to store everyone's information:

typedef struct tagPartner
{
	string name;   //Name
	int next = 0;     //Next match
	int current = -1;  //Current pairing, - 1 means no pairing yet
	int pCount = UNIT_COUNT; //Number of favors in the list
	int* perfect = new int[UNIT_COUNT]; //Favorable list
}PARTNER;

② . find the perfect match and judge whether it is stable (main algorithm)

//Main algorithm part
void SearchStableMatch(int index, PARTNER *boys, PARTNER *girls)
{
	//If index = = Unit Ou count, it indicates that a set of perfect matching is successful and whether it is stable
	if (index == UNIT_COUNT)
	{
		if (IsStableMatch(boys, girls))//Judge whether it is a stable match
		{
			PrintResult(boys, girls, UNIT_COUNT);//Printing
		}
		return;
	}

	//Match the boy with index, i.e. find the perfect match
	for (int i = 0; i < boys[index].pCount; i++)
	{
		int gid = boys[index].perfect[i];//boy matching girl number

		if (!IsPartnerAssigned(&girls[gid]) && IsFavoritePartner(&girls[gid], index))//If girl gid has no objects, and index man is in her favorite list
		{
			boys[index].current = gid;//Match index men and gid women into a group
			girls[gid].current = index;
			SearchStableMatch(index + 1, boys, girls);//For the next man

			//The following two statements are the end of the recursive call, that is, a statement executed after a perfect match succeeds
			//Return to single status
			boys[index].current = -1;
			girls[gid].current = -1;
		}
	}
}

③ . judge whether the perfect match is stable

//Judge whether the match is stable
bool IsStableMatch(PARTNER *boys, PARTNER *girls)
{
	for (int i = 0; i < UNIT_COUNT; i++)
	{
		//Find the position of the boy's current match in his preference list
		int gpos = GetPerfectPosition(&boys[i], boys[i].current);
		//Before the position position, boys like them better than current
		for (int k = 0; k < gpos; k++)
		{
			int gid = boys[i].perfect[k];
			//Find the boy's place in the girl's liking list
			int bpos = GetPerfectPosition(&girls[gid], i);
			//Find the location of the girl's current partner in the girl's liking list
			int cpos = GetPerfectPosition(&girls[gid], girls[gid].current);
			if (bpos < cpos)
			{
				//Girls also like this boy better than their current partners, which is a factor of instability
				return false;
			}
		}
	}
	return true;
}

④ . other auxiliary functions

//Get the position of the person with id in the partner preference list
int GetPerfectPosition(PARTNER *partner, int id)
{
	for (int i = 0; i < partner->pCount; i++)
	{
		if (partner->perfect[i] == id)
		{
			return i;
		}
	}//Returns a very large value, which means it doesn't match the right value at all
	return 9999999;
}

void PrintResult(PARTNER *boys, PARTNER *girls, int count)
{
	for (int i = 0; i < count; i++)
	{
		out << boys[i].name << "<---> " << girls[boys[i].current].name << endl;
	}
	out << "========== " << endl;
}

//Judge whether the partner has objects
bool IsPartnerAssigned(PARTNER *partner)
{
	return (partner->current != -1);
}

//Judge whether the boy bid is the girl partner's favorite
bool IsFavoritePartner(PARTNER *partner, int bid)
{
	for (int i = 0; i < partner->pCount; i++)
	{
		if (partner->perfect[i] == bid)
		{
			return true;
		}
	}
	return false;
}

3. Optimize input and output:
Change the I / O to read in and read out of the file, for example:

Import file style:

4 / / number of people
 ==========/ / separator
 Three Zhang, four Li, four Wang, six Zhang, five / / space off the dating list (male side)
One flower, two flowers, three flowers and six flowers / / space off the blind date list (female side)
==========/ / separator
 2 3 1 0 / * sorting of the number of men's favorite girls, for example, the first line:
The most favorite girl of the boy (Zhang San) was No.2 (ER NAI), and the next was No				
0 23 1 3 (Sanhua), according to this rule
1 3 2 0                  */
==========
0.3.2 1 / / the ranking of the number of boys that the woman likes is the same as that of boys
0 1 2 3
0 2 3 1
1 0 3 2

Output file style: output all cases with good matching, divided by ====================(only one stable matching exists in this column)

Zhang San < --- > Sanhua
 Li Si
 Wang Liu
 Zhang Wu < --- > six flowers
========== 

Total code:

#include <stdio.h>
#include <cassert>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include<string>
#include <fstream>
using namespace std;
int UNIT_COUNT;
ofstream out("C:\\Users\\26216\\Desktop\\stable\\output.txt");
typedef struct tagPartner
{
	string name;   //Name
	int next = 0;     //Next match
	int current = -1;  //Current pairing, - 1 means no pairing yet
	int pCount = UNIT_COUNT; //Number of favors in the list
	int* perfect = new int[UNIT_COUNT]; //Favorable list
}PARTNER;


//Get the position of the person with id in the partner preference list
int GetPerfectPosition(PARTNER *partner, int id)
{
	for (int i = 0; i < partner->pCount; i++)
	{
		if (partner->perfect[i] == id)
		{
			return i;
		}
	}//Returns a very large value, which means it doesn't match
	return 9999999;
}

void PrintResult(PARTNER *boys, PARTNER *girls, int count)
{
	for (int i = 0; i < count; i++)
	{
		out << boys[i].name << "<---> " << girls[boys[i].current].name << endl;
	}
	out << "========== " << endl;
}

//Judge whether the partner has objects
bool IsPartnerAssigned(PARTNER *partner)
{
	return (partner->current != -1);
}

//Judge whether the boy bid is the girl partner's favorite
bool IsFavoritePartner(PARTNER *partner, int bid)
{
	for (int i = 0; i < partner->pCount; i++)
	{
		if (partner->perfect[i] == bid)
		{
			return true;
		}
	}
	return false;
}

//Judge whether the match is stable
bool IsStableMatch(PARTNER *boys, PARTNER *girls)
{
	for (int i = 0; i < UNIT_COUNT; i++)
	{
		//Find the position of the boy's current match in his preference list
		int gpos = GetPerfectPosition(&boys[i], boys[i].current);
		//Before the position position, boys like them better than current
		for (int k = 0; k < gpos; k++)
		{
			int gid = boys[i].perfect[k];
			//Find the boy's place in the girl's liking list
			int bpos = GetPerfectPosition(&girls[gid], i);
			//Find the location of the girl's current partner in the girl's liking list
			int cpos = GetPerfectPosition(&girls[gid], girls[gid].current);
			if (bpos < cpos)
			{
				//Girls also like this boy better than their current partners, which is a factor of instability
				return false;
			}
		}
	}
	return true;
}

//Main algorithm part
void SearchStableMatch(int index, PARTNER *boys, PARTNER *girls)
{
	//If index = = Unit Ou count, it indicates that a set of perfect matching is successful and whether it is stable
	if (index == UNIT_COUNT)
	{
		if (IsStableMatch(boys, girls))//Judge whether it is a stable match
		{
			PrintResult(boys, girls, UNIT_COUNT);//Printing
		}
		return;
	}

	//Match the boy with index, i.e. find the perfect match
	for (int i = 0; i < boys[index].pCount; i++)
	{
		int gid = boys[index].perfect[i];//boy matching girl number

		if (!IsPartnerAssigned(&girls[gid]) && IsFavoritePartner(&girls[gid], index))//If girl gid has no objects, and index man is in her favorite list
		{
			boys[index].current = gid;//Match index men and gid women into a group
			girls[gid].current = index;
			SearchStableMatch(index + 1, boys, girls);//For the next man

			//The following two statements are the end of the recursive call, that is, a statement executed after a perfect match succeeds
			//Return to single status
			boys[index].current = -1;
			girls[gid].current = -1;
		}
	}
}

int main(int argc, char* argv[])
{
	ifstream in("C:\\Users\\26216\\Desktop\\stable\\input.txt");
	in >> UNIT_COUNT;
	string* bName = new string[UNIT_COUNT];
	string* gName = new string[UNIT_COUNT];
	PARTNER* boys = new PARTNER[UNIT_COUNT];
	PARTNER* girls = new PARTNER[UNIT_COUNT];
	in.seekg(12, ios::cur);
	for (int i = 0; i < UNIT_COUNT; i++)
		in >> bName[i];
	for (int j = 0; j < UNIT_COUNT; j++)
		in >> gName[j];
	in.seekg(12, ios::cur);
	for (int i = 0; i < UNIT_COUNT; i++)
		for (int j = 0; j < UNIT_COUNT; j++)
			in >> boys[i].perfect[j];
	in.seekg(12, ios::cur);
	for (int i = 0; i < UNIT_COUNT; i++)
		for (int j = 0; j < UNIT_COUNT; j++)
			in >> girls[i].perfect[j];
	for (int i = 0; i < UNIT_COUNT; i++)
	{
		boys[i].name = bName[i];
		girls[i].name = gName[i];
	}
	in.close();
	SearchStableMatch(0, boys, girls);
	out.close();
	return 0;
}

Additional:
Here is a bit of java code. It is not input according to the file:

class PARTNER{
	public static int UNIT_COUNT;//Number of boys or girls
	public String name;	//Name
	public int next;		//Next invited
	public int current;	//Current object number
	public int pCount;		//Number of people in preference table
	public int []perfect=new int[UNIT_COUNT];//Preference list
	
	public PARTNER(String name,int next,int current,int pCount,int []perfect) {
		this.name=name;
		this.current=current;
		this.pCount=pCount;
		this.perfect=perfect;
	}
}

public class marriage {
	
	int GetPerfectPosition(PARTNER partner, int id)
	{
		for (int i = 0; i < partner.pCount; i++)
		{
			if (partner.perfect[i] == id)
			{
				return i;
			}
		}//Returns a very large value, which means it's not right at all
		return 0x7FFFFFFF;
	}

	void PrintResult(PARTNER []boys, PARTNER []girls, int count)
	{
		System.out.println("Results after pairing:");
		for (int i = 0; i < count; i++)
		{
			System.out.println( boys[i].name + "<---> " + girls[boys[i].current].name );
		}
		System.out.println("================");
	}

	boolean IsPartnerAssigned(PARTNER partner)
	{
		return (partner.current != -1);
	}

	boolean IsFavoritePartner(PARTNER partner, int bid)
	{
		for (int i = 0; i < partner.pCount; i++)
		{
			if (partner.perfect[i] == bid)
			{
				return true;
			}
		}
		return false;
	}

	boolean IsStableMatch(PARTNER []boys, PARTNER []girls)
	{
		for (int i = 0; i < PARTNER.UNIT_COUNT; i++)
		{
			//Find out where the boy's current partner is on his preference list
			int gpos = GetPerfectPosition(boys[i], boys[i].current);
			//Boys like their partners before position more than current
			for (int k = 0; k < gpos; k++)
			{
				int gid = boys[i].perfect[k];
				//Find the boy's place in the girl's preference list
				int bpos = GetPerfectPosition(girls[gid], i);
				//Find out where the girl's current partner is on the girl's preference list
				int cpos = GetPerfectPosition(girls[gid], girls[gid].current);
				if (bpos < cpos)
				{
					//Girls also like this boy better than their current partners, which is a factor of instability
					return false;
				}
			}
		}
		return true;
	}

	public void SearchStableMatch(int index, PARTNER []boys, PARTNER []girls)
	{
		if (index == PARTNER.UNIT_COUNT)
		{
			if (IsStableMatch(boys, girls))
			{
				PrintResult(boys, girls, PARTNER.UNIT_COUNT);
			}
			return;
		}
	
		for (int i = 0; i < boys[index].pCount; i++)
		{
			int gid = boys[index].perfect[i];
	
			if (!IsPartnerAssigned(girls[gid]) && IsFavoritePartner(girls[gid], index))
			{
				boys[index].current = gid;
				girls[gid].current = index;
				SearchStableMatch(index + 1, boys, girls);
				boys[index].current = -1;
				girls[gid].current = -1;
			}
		}
	}

	public static void main(String[] args) {
		
		PARTNER.UNIT_COUNT=3;
		PARTNER [] boys=new PARTNER[3];
		PARTNER [] girls=new PARTNER[3];
		
		int []a= {2,0,1};
		PARTNER boy1=new PARTNER("Zhang San", 0, -1, 3, a);
		int []b= {0,2,1};
		PARTNER boy2=new PARTNER("Li Si", 0, -1, 3, b);
		int []c= {1,0,2};
		PARTNER boy3=new PARTNER("Wang Wu", 0, -1, 3, c);
		
		int []ga= {0,2,1};
		PARTNER girl1=new PARTNER("A flower", 0, -1, 3, ga);
		int []gb= {1,2,0};
		PARTNER girl2=new PARTNER("Erhua", 0, -1, 3, gb);
		int []gc= {0,1,2};
		PARTNER girl3=new PARTNER("Three flowers", 0, -1, 3, gc);
		
		boys[0]=boy1;
		boys[1]=boy2;
		boys[2]=boy3;
		
		girls[0]=girl1;
		girls[1]=girl2;
		girls[2]=girl3;
		
		marriage m=new marriage();

		m.SearchStableMatch(0, boys, girls);
	}

}

Output results:

Results after pairing:
Zhang San
 Li Si < --- > Yihua
 Wang Wu
================
Results after pairing:
Zhang San
 Li Si
 Wang Wu
================

Reference: the fun of algorithm, Wang Xiaohua, people's post and Telecommunications Press